Алгоритм
Started By OzzY, мар 21 2006 18:19
10 ответов в этой теме
#1
Отправлено 21 марта 2006 - 18:19
Привет.
Как бы вы реализовали такую задачу(ваш алгоритм)?:
Задано некоторое число(например 15), дано определенное количество других чисел, например,
2-две штуки,
3-5 штук,
1-10 штук,
7-одна штука.
...и т.д.
Число задает пользователь количество цифр и какие цифры, тоже задает пользователь. Нужно найти все возможные варианты составить это число из имеющихся. В данном случае(чтобы составить 15):
возьмем
10 и 1 -пять штук; или
10, 3, 2; или
7, 3- две штуки, 2;
и т.д.
Есть мысли?
Как бы вы реализовали такую задачу(ваш алгоритм)?:
Задано некоторое число(например 15), дано определенное количество других чисел, например,
2-две штуки,
3-5 штук,
1-10 штук,
7-одна штука.
...и т.д.
Число задает пользователь количество цифр и какие цифры, тоже задает пользователь. Нужно найти все возможные варианты составить это число из имеющихся. В данном случае(чтобы составить 15):
возьмем
10 и 1 -пять штук; или
10, 3, 2; или
7, 3- две штуки, 2;
и т.д.
Есть мысли?
#2
Отправлено 22 марта 2006 - 12:14
ну очевидно такое решение
Интереснее когда надо проверить возможность разложения или найти только одно разложение ,, тогда решается не перебором..
#include <iostream> using namespace std; #define _MAX 100 int c[_MAX + 1]; int u[_MAX + 1]; int a; void rec(int n, int k) { if (n == 0) { cout << a << " = "; bool first = true; for (int i = 1; i <= _MAX; i++) for (int j = 1; j <= u[i]; j++) { if (first) cout << i; else cout << "+" << i; first = false; } cout << endl; } else { for (int i = k; i <= _MAX; i++) { if ((c[i] > 0) && (n - i >= 0)) { c[i]--; u[i]++; rec(n - i, i); u[i]--; c[i]++; } } } } int main() { memset(c, 0, sizeof(c)); memset(u, 0, sizeof(u)); c[2] = 2; c[3] = 5; c[1] = 10; c[7] = 1; a = 15; rec(a, 1); }
Интереснее когда надо проверить возможность разложения или найти только одно разложение ,, тогда решается не перебором..
#6
Отправлено 24 марта 2006 - 01:57
OzzY, хе. Это надо вспомнить формулы перестановок, найти листочек бумаги и ручку. Если решу, выложу. А сегодня я умаялся уж.
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!
#8
Отправлено 27 марта 2006 - 11:27
OzzY, извини. У меня усилок погорел, я уже неделю кроме паяльника ничего не вижу
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!
#10
Отправлено 27 марта 2006 - 15:44
V^v, я код не смотрел, но автор говорит что решается перебором. Здесь, мое скромное имхо можно без перебора обойтись...
Моя Родина - СССР! Пролетарии всех стран, соединяйтесь!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!
-----------------------------------------------------------------------
Ясность - одна из форм полного тумана. Форумчане, давайте жить дружно!