Привет мастера!
есть такая задачка!
дано числа p, m;
требуется сгенерировать всевозможные наборы из m+1 чисел, числа берутся из множества {0,1,2..p-1}.
Например :
p=3 -> числа следующие: {0,1,2} m=например 2
значит нужно сформировать все комбинации из трех чисел:
{0,0,0}{0,0,1}{0,0,2}{0,1,0}{0,2,0}{0,1,1}{0,1,2}{0,2,1}{0,2,2} и т.д.

Изаписать их в двумерный массив в котором ь+1 столбец
и P^m рядков

из примера:
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
.......
2 2 1
2 2 2

Подскажите как это сделать. я не могу придумать!

и еще если можно подскажите какова сложность этого алгоритма

поиском пользовался! нашел какой-то похожий алгоритм, но разобраться даже с ним не смог
ссылка на него -> http://algolist.manual.ru/olimp/per_prb.php

спасибо. жду ответа

а это и не тот алгоритм...
там, насколько я понял, имеется в виду выборка без повторений (сам думал предложить ссылку на тему, в которойэто обсуждалось)
здесь - выборка с повторениями и учетом порядка (если порядок следования элементов разный, выборки считаются разными)

в данном случае стоит посмотреть на это, как на запись числа в p-ичной системе счисления
например, при p=10 мы получаем задачу вывода всех m+1-значных десятичных чисел
в общем случае можно просто перебрать все числа, выбрав первое (0,0,...,0) и прибавляя к нему 1-цу по обычным правилам (с переносом на следующие разряды и все такое)
т.е получается что-то типа:

Алгоритм:

а на pascal можно как-то? я си не понимаю вааще

а это и не C
если возникли проблемы с реализацией алгоритма или переводом с языка на язык - лучше писать в форум по этому языку или в Центр помощи...

это я не очень представляю.. что это значит

_snikers_, Это означает следующее:

Берем очередное i. Например это 11. Количество чисел у нас 6. преобразуем 11 в битовое (двоичное) представление. Получаем 1011. Т.к. чисел 6, добиваем спереди нулями, получая 001011. Т.е. в наборе номер 11 будут присутствовать только числа с порядковым номером 0, 1 и 3 (там единицы) и НЕ будут присутствовать 2, 4, 5 - ибо там нули.

стоп-стоп-стоп...
мне кажется, это не совсем то, что требовалось в задаче:
в данном случае получается выборка всевозможных подмножеств чисел от 0 до m-1
при чем тут p тогда?
ведь если i будет всегда меньше 2^m, то len(si) будет всегда меньше m
а это означает, что числа будут выбираться из промежутка 0..m-1, а не 0..p-1
кроме того количество чисел в наборе будет варьироваться от 0 до m-1, что совсем не соответствует условию задачи - количество должно быть постоянным

правильно


а вот это неправильно!
я может неправильно написал! но давайте еще раз!
р = это те цифры котрые будут во всех возможных комбинациях из m+1 ЦИФР!
например
p=3, m=4 -> отсюда нужно найти все возможные наборы из m+1(тоесть 4+1=5) цифр значение которых может быть только 0 или 1 или 2 (потому что p=3)

это будет в нашем случае такие
00000
00001
00002
00010
00011
00012
00020
.....
22222
надеюсь тепер понятно
P.S.
блин замучила эта задача
курсовая через 3 недели

это относилось к алгоритму, к которому относилось сообщение, а не к условию задачи

to maxim1000
извиняюсь

Да... согласен, был невнимателен.

Вот рабочий, проверенный, код на VB6:

пасибо всем! задание решил!

Respect to maxim1000 + немного благодарности (после 100 постов :-))

если интересует как решено, пишите на мыло.

Это сообщение отредактировал(а) _snikers_ - 8.4.2006, 12:57

Согласен. Соотвественно и алгоритм следующий:
цикл от 1 до p^(m+1)
перевод счетчика в p-ичную систему счисления
добавление результата в массив
конец цикла