Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > задача на получение всевозможных наборов

Автор: _snikers_ 5.4.2006, 00:16

Привет мастера! есть такая задачка! дано числа 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 спасибо. жду ответа

Автор: maxim1000 5.4.2006, 01:07

Цитата(_snikers_ @ 4.4.2006, 23:16 ) поиском пользовался! нашел какой-то похожий алгоритм, но разобраться даже с ним не смог ссылка на него -> http://algolist.manual.ru/olimp/per_prb.php а это и не тот алгоритм... там, насколько я понял, имеется в виду выборка без повторений (сам думал предложить ссылку на тему, в которойэто обсуждалось) здесь - выборка с повторениями и учетом порядка (если порядок следования элементов разный, выборки считаются разными) в данном случае стоит посмотреть на это, как на запись числа в p-ичной системе счисления например, при p=10 мы получаем задачу вывода всех m+1-значных десятичных чисел в общем случае можно просто перебрать все числа, выбрав первое (0,0,...,0) и прибавляя к нему 1-цу по обычным правилам (с переносом на следующие разряды и все такое) т.е получается что-то типа: Код bool Add1(int *array,int m,int p,int degree) {   ++array[degree];//увеличиваем разряд   if(array[degree]==p)//если некуда увеличивать,   {     array[degree]=0;//сбрасываем в 0     if(degree==m)//все, прошли все m+1 разряда (от 0 до m)       return false;     else       return Add1(array,m,p,degree+1);//увеличиваем следующий разряд   }   else     return true; } ... //использование: //выводим все 10-значные числа в 5-чной системе счисления int array[10]={0,0,0,0,0,0,0,0,0,0}; while(true) {   PrintArray(array);   if(Add1(array,9,5,0))     break; }

Автор: Akina 5.4.2006, 10:19

Алгоритм: Код Цикл по i от 0 до 2^m-1    Преобразовать i в битовое представление в строку si    Начать очередной набор    Цикл по j от 0 до len(si)-1       Если j-й символ строки si = "1", включить p(j) в очередной набор.    Конец цикла    Закончить и вывести очередной набор Конец цикла

Автор: _snikers_ 5.4.2006, 12:58

Код Цикл по i от 0 до 2^m-1    Преобразовать i в битовое представление в строку si    Начать очередной набор    Цикл по j от 0 до len(si)-1       Если j-й символ строки si = "1", включить p(j) в очередной набор.    Конец цикла    Закончить и вывести очередной набор Конец цикла а на pascal можно как-то? я си не понимаю вааще

Автор: maxim1000 5.4.2006, 13:57

Цитата(_snikers_ @ 5.4.2006, 11:58 ) а на pascal можно как-то? я си не понимаю вааще а это и не C если возникли проблемы с реализацией алгоритма или переводом с языка на язык - лучше писать в форум по этому языку или в Центр помощи...

Автор: _snikers_ 5.4.2006, 22:59

Код Преобразовать i в битовое представление в строку si это я не очень представляю.. что это значит

Автор: Akina 6.4.2006, 09:23

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

Автор: maxim1000 6.4.2006, 10:58

Цитата(Akina @ 6.4.2006, 08:23 ) Берем очередное 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, что совсем не соответствует условию задачи - количество должно быть постоянным

Автор: _snikers_ 6.4.2006, 19:54

Код мне кажется, это не совсем то, что требовалось в задаче: правильно Код а это означает, что числа будут выбираться из промежутка 0..m-1, а не 0..p-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 недели

Автор: maxim1000 6.4.2006, 22:34

Цитата(_snikers_ @ 6.4.2006, 18:54 ) а вот это неправильно это относилось к алгоритму, к которому относилось сообщение, а не к условию задачи

Автор: _snikers_ 6.4.2006, 23:53

to maxim1000 извиняюсь

Автор: Akina 7.4.2006, 09:29

Цитата(maxim1000 @ 6.4.2006, 11:58 ) стоп-стоп-стоп... мне кажется, это не совсем то, что требовалось в задаче: Да... согласен, был невнимателен. Вот рабочий, проверенный, код на VB6: Код ' Определение переменных Dim m As Integer Dim p As Integer Dim i As Integer Dim cur As Integer Dim ar() As Integer ' Задание начальных значений m = 2 p = 2 ' переопределение массива по начальным условиям ReDim ar(m+1) ' Ручное составление первого набора For i = 0 To m+1    ar(i) = 0 Next i ' Основной цикл Do ' Вывод очередного набора    For i = 0 To m+1       Debug.Print ar(i);    Next i    Debug.Print ' Составление следующего набора    cur = m+1    Do While ar(cur) = p - 1       cur = cur - 1 ' Тут - проверка на получение всех наборов       If cur < 0 Then End    Loop    ar(cur) = ar(cur) + 1    For i = cur + 1 To m+1       ar(i) = 0    Next i Loop

Автор: _snikers_ 8.4.2006, 12:55

пасибо всем! задание решил! Respect to maxim1000 + немного благодарности (после 100 постов :-)) если интересует как решено, пишите на мыло.

Автор: Заппер 8.4.2006, 16:38

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)