Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.216.121.55] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Всем привет!
Есть такая задачка: Дано N объектов (N = [1 .. 6]), которые могут принимать M значений (M = [1 .. 5]). Получить все возможные перестановки/размещения с повторениями данных объектов. Для примера, если N = 4, M = 3, то код может быть таким (если заранее жестко известны значения N, M): #include "stdafx.h" #include <iostream> using namespace std; const int M = 3; int main() { long long n = 0; for(int i = 1; i <= M; i++) for(int j = 1; j <= M; j++) for(int k = 1; k <= M; k++) for(int l = 1; l <= M; l++) cout << ++n << ":\t" << i << j << k << l << endl; cin.get(); return 0; } Получается 81 цепочка, что соответствует формуле из комбинаторики размещения с повторениями = M^N = 3^4 = 81 набор. Но это тупой, топорный, абсолютно негибкий вариант, т к N, M будут задаваться динамически во время выполнения программы. В этом алгоритме полного перебора к чему стремиться? К построению дерева, к рекурсии или еще как-то? P.S. находил описания в сети чего-то похожего + даже код был на Паскале, но глубоко не могу понять этот алгоритм... |
Сообщ.
#2
,
|
|
|
Рекурсия?
|
Сообщ.
#3
,
|
|
|
Цитата Akina @ Рекурсия? ну, допустим, да! но я не понимаю, как через нее сделать P.S. максимально вызовов будет 5^6 = 25^3 = 15 625 рекурсивной функции. Это ведь вроде немного... |
Сообщ.
#4
,
|
|
|
Цитата FasterHarder @ я не понимаю, как через нее сделать Передаёшь в функцию текущий недовариант и уровень. Если уровни вычерпаны - выводишь, иначе дописываешь по одному элементу и шлёшь на следующий виток. |
Сообщ.
#5
,
|
|
|
Как вариант вместо рекурсии - непосредственная генерация следующего элемента. Как-то так:
const int N = 6, M = 5; int a[N]; for(int i = 0; i < N; ++i) a[i] = 1; do { for(int i = 0; i < N; ++i) std::cout << a[i] << " "; int i = 0; while(i < N && a[i] == M) { a[i] = 1; ++i; } if(i == N) break; ++a[i]; } while(true); Добавлено И то, что тебе надо, называется не перестановками, а размещениями с повторением. |
Сообщ.
#6
,
|
|
|
Народ, какая рекурсия? Это же просто получение записи всех чисел от 0 до M^N-1 в M-ричной системе счисления с заменой символов "0" на "1", "1" на "2" и т. д.
Вот на бейсике: Sub Main() Dim N As Long, M As Long Dim i As Long, ii As Long, j As Long, Cnt As Long Dim Res As String N = 4 M = 3 Cnt = M ^ N For i = 1 To Cnt ii = i Res = "" For j = 0 To M Res = Res & Chr(49 + (ii Mod M)) ii = ii \ M Next j Debug.Print Res Next i End Sub |
Сообщ.
#7
,
|
|
|
А, допустим, не знали бы мы, что получится их 34; как бы ваш код, Mikle, изменился?..
|
Сообщ.
#8
,
|
|
|
Он бы просто новые значения N и M подставил. Другое дело, что конкретно эта программа (на бейсике или транслированная на подавляющее большинство ЯП) не любую комбинацию N, M потянет.
В отличие от программы OpenGL, которая получилась такой же короткой и быстрой (будучи реализованными на одном языке эта программа скорее всего окажется даже быстрее), и где тоже достаточно поменять значения N, M. |
Сообщ.
#9
,
|
|
|
Цитата amk @ Я не понял ваш ответ, amk. Если бы мы не знали, что итог - это возведение числа в степень другого числа, то как бы изменилась прога Mikle? Он бы просто новые значения N и M подставил. |
Сообщ.
#10
,
|
|
|
Так, давайте еще внесем НЕБОЛЬШУЮ ясность! Забыл написать об этом изначально)
Вывод должен быть в лексикографическом порядке, поэтому код из поста №5 нужно допиливать! Да, может быть чуть-чуть, но нужно! P.S. Для натуральных чисел лексикографический порядок выводит по возрастанию 1111 1112 1113 1121 .... 3333 Добавлено И это, давайте поменьше кода и побольше алгоритмизации, т к поняв алгоритм, я как бы сам должен суметь закодить! Ну, это в идеале. А на практике уйдет не один месяц, чтобы понять глубоко данный алгоритм. Добавлено Предпочтение отдается рекурсии! Akina поверхностно объяснил (дал идею), буду думать... |
Сообщ.
#11
,
|
|
|
Цитата FasterHarder @ Вывод должен быть в лексикографическом порядке, поэтому код из поста №5 нужно допиливать! В п.6 именно так. И идея там изложена, не только код: Цитата Это же просто получение записи всех чисел от 0 до M^N-1 в M-ричной системе счисления с заменой символов "0" на "1", "1" на "2" и т. д. Цитата Славян @ А, допустим, не знали бы мы, что получится их 34; как бы ваш код, Mikle, изменился? Если бы я этого не знал, через минуту я бы уже до этого сам догадался. |
Сообщ.
#12
,
|
|
|
Цитата Славян @ А подумать немного, перед тем как нажимать клавиши? Разработка алгоритмов тем и отличается, что над ним сначала долго думаешь, потом относительно быстро пишешь программу. Если бы мы не знали, что итог - это возведение числа в степень другого числа |
Сообщ.
#13
,
|
|
|
Цитата FasterHarder @ Вывод должен быть в лексикографическом порядке, поэтому код из поста №5 нужно допиливать! Да, может быть чуть-чуть, но нужно! Просто иди во внутреннем while не от 0 до N, а наоборот. Ну или просто выводи их в перевёрнутом виде. |
Сообщ.
#14
,
|
|
|
Народ резко бросился прогать!
Цитата FasterHarder @ Так, давайте еще внесем НЕБОЛЬШУЮ ясность! А давайте! Так всеж или перестановки нужны? Или размещения? Туманишь ты народ непадецки Термины разные, расчеты разные ... определись, что именно нужно! |
Сообщ.
#15
,
|
|
|
В условии написано, что размещения с повторениями!
Вот заготовка программы на С++(там нет главного): #include "stdafx.h" #include <iostream> using namespace std; //---------------------------------------------------- // Вывод последовательности цифр на экран //---------------------------------------------------- void PrintSequence(const int* const pv, const int pcount, const int pID) { cout << pID << ":\t"; for(register int i = 0; i < pcount; i++) cout << pv[i]; } //---------------------------------------------------- int main() { setlocale(LC_ALL, ""); cout << "Введите количество объектов/цифр для обработки из отрезка [2 .. 6]: "; int count; cin >> count; cout << "Введите максимальное значение, принимаемое цифрой, из отрезка от [2 .. 9]: "; int maxValue; cin >> maxValue; int *v = new int[count]; // инициализация всех цифр значением 1 for(int i = 0; i < count; i++) v[i] = 1; int ID = 0; PrintSequence(v, count, ++ID); cin.get(); cin.get(); delete []v; // динамический массив нужно уничтожить при выходе из программы! return 0; } Т е в программу подается количество цифр в последовательности + диапазон значений(левая граница = 1 - присваивается при инициализации). Т к нужна рекурсия, то я хочу понять, что является элементарным случаем рекурсии. Например, когда рассчитывается факториал числа, то элементарным случаем является такое условие: if(pn < 2) return 1; если делается обход бинарного дерева поиска, то элементарный случай возникает тогда, когда текущий узел является ЛИСТОМ. А, что в данном случае является элементарным случаем рекурсии? Когда все цифры стали равны maxValue? |