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

Форум программистов > Центр помощи > [Комбинаторика | C++] Комбинации без повторений

Автор: apook 7.1.2007, 03:45

На днях тут решали задачку возникла задачя попроще даны числа 12345 найти количество комбинаций разных которые можно составить из этих чисел чтоб все цифры присутствовали. M Kuvaldis НА будущее: название темы должно отражать ее суть! Да и область знаний указывать нужно... :)

Автор: AlexArs 7.1.2007, 04:22

Выбирай : http://imageshack.us Формулы: http://imageshack.us

Автор: apook 7.1.2007, 06:59

Обоснуйте пожалуйста формулу Без повторений, а то для меня  выглядит как потому-что.

Автор: AlexArs 7.1.2007, 07:26

apook,  http://imageshack.us Код Пример: Правильно: 12345 13245 54231 Неправильно: 11234 13225 33423 т.е. в размещении без повторений цифра повторятся не может!!! понел ?

Автор: apook 7.1.2007, 08:30

Я тут  придумал свой способ и в нем мне достаточно знать что что каждая цифра числа когда то будет  первой и  это  будет повторяться n-раз Код #include "stdio.h" #include "stdlib.h" #include "conio.h" void main( int argc, char *argv[] ) { int a, i, j, x, *number; a=5; number =( int * ) malloc ( (a+1)*sizeof(int) ); /* ********** */ for( i=0; i <a; i++ )     number[i] -i; for( i=0; i <a-1; i++ ); for( j=1, x=1; j <=i; j++ )      x=x*j; x=x*a; /* ********** */ printf( "%d\n", x ); getch(); return; }

Автор: AlexArs 7.1.2007, 08:35

apook,  Тебе че надо это в С++ сделать?  На будущее: Цитата Первым делом в квадратных скобках укажи область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++]. Для нескольких языков для краткости используй: [C++|Delphi] -- "или", [C++&Delphi] -- "и", [C++->Delphi] -- "в".  А то я использовал комбинаторику!!!

Автор: apook 7.1.2007, 09:30

Не все нормально мне важна суть а в код просто перевел ради Demo Да я и не знаю как в комбинаторике изобразить x=1 x=x+x=2 x=x+x+x=6 x=x+x+x+x=24 и т.д именно так выглядит изобретенный мной способ

Автор: apook 7.1.2007, 09:53

Вот полностью n=(общее количество цифер) - 1 x=1 x=x+x=2 x=x+x+x=6 x=x+x+x+x=24 и так делать пока n раз затем x * n . как будет в комбинаторике

Автор: AlexArs 7.1.2007, 10:09

apook,  К твоей задаче можно использовать формулу: A = n!, где n - количество цифр в числе, А - кол-во комбинаций. Нельзя использовать 0 (будет уже другая формула) Добавлено @ 10:17  apook,  А=(n-1)!*(n-1) где n - количество цифр в числе, А - кол-во комбинаций. Эта формула если среди данных цифр есть 0.

Автор: apook 7.1.2007, 10:25

Я извиняюсь что я дубовый но я ни че не понял мне надо сделать именно то что я написал  там не будет ни каких повторений(однако) Цитата где n - количество цифр в числе, А - кол-во комбинаций. помоему это немного другой смысл(надо подумать) у меня x это количество повторений одной цифры (первой на момент когда в числе n+1 цифр) +1 это как-раз для той цифры  Реши пожалуйста не меняя смысла

Автор: AlexArs 7.1.2007, 10:55

Если тебе нужна программа для того чтобы считала количество комбинаций из n чисел, то: Если среди цифр есть 0, то  A = n!, где n - количество цифр в числе, А - кол-во комбинаций. Если среди цифр нет 0, то А=(n-1)!*(n-1) где n - количество цифр в числе, А - кол-во комбинаций. Примеры, например n=4: Цифры: 0,1,2,3. Найти количество разных комбинаций которые можно составить из этих чисел чтоб все цифры присутствовали. A=4!=(4-1)!*(4-1)=3!*3=1*2*3*3=18, или http://imageshack.us Первой число размещений из 3 по 1, а не из 4по 1 потому, что число на ноль не начинается! Цифры: 1,2,3,4. Найти количество разных комбинаций которые можно составить из этих чисел чтоб все цифры присутствовали. A=4!=1*2*3*4=24, или http://imageshack.us Если непонел пиши !

Автор: AlexArs 7.1.2007, 11:08

Тебе надо чтобы считало по комбинации чисел или по комбинации цифр, т.е. n-значных чисел или последовательность цифр? Код Например цифры:0,2,3,4,5,6 : n=6, 402536 - число  320456 - число 023465 - последовательность цифр (не число) 065234 - последовательность цифр (не число)

Автор: apook 7.1.2007, 11:20

Спасибо большое AlexArs за разжевывание и  за участие но вот  меня заинтересовали не стандартные решения,  как еще можно подойти к решению  произошло это потому, что я еще ког да не  знал этого решения 5*4*3*2*1, сдуру  придумал  свое и оно функционально. И как ты понимаешь оно (почему-бы это) мне нравится  больше чем оффициальное(по правильной формуле). Всвязи с этим может кому-то нечего делать(как мне)попробуйте решить ету задачю другим путем БУДУ РАД ЛЮБЫМ ИДЕЯМ Цитата Тебе надо чтобы считало по комбинации чисел или по комбинации цифр, т.е. n-значных чисел или последовательность цифр? последовательность цифр

Автор: Pete 7.1.2007, 16:04

Цитата(apook @  7.1.2007,  04:45 ) На днях тут решали задачку возникла задачя попроще даны числа 12345 найти количество комбинаций разных которые можно составить из этих чисел чтоб все цифры присутствовали. Если я правильно понял, то условие звучит так: Код Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5 так, чтобы ни одна из них не повторялась? Цитата(apook @  7.1.2007,  12:20 ) мне нравится  больше, чем официальное (по правильной формуле) Что значит «официальное»? Любое решение будет правильным, если ты сможешь его объяснить. По-моему, вообще лучше не запоминать некоторых простейших формул из комбинаторики (размещения, перестановки). Смотри: у нас есть 5 позиций и 5 цифр. На 1-ю позицию можно поставить любую из этих 5-ти (5 вариантов), после чего останется уже 4 цифры и 4 свободные позиции. На 2-ю позицию можно поставить любую из 4-х оставшихся (4 варианта), причем независимо от 1-ой позиции. ... На 1-ю позицию можно поставить только 1-ну оставшуюся цифру, то есть только одним единственным способом. Так как постановки на каждую позицию независимы друг от друга, мы (по теореме умножения) перемножаем получившиеся количества вариантов: P = 5*4*3*2*1 = 5! = 120. Цитата(apook @  7.1.2007,  10:30 ) x=1 x=x+x=2 x=x+x+x=6 x=x+x+x+x=24 и т.д именно так выглядит изобретенный мной способ В чем заключается твой способ?   Добавлено @ 16:09  Кажется, понял. Формально он ничем не отличается от факториала: Код x1 = 1 = 1!, x2 = 2*x1 = 2*1 = 2!, x3 = 3*x2 = 3*2*1 = 3!, x3 = 4*x3 = 4*3*2*1 = 4! ... Только вот как ты это объяснять собираешься, и что такое x??..

Автор: AlexArs 7.1.2007, 16:38

Цитата(apook @  7.1.2007,  18:20 ) последовательность цифр A = n! - получается эта формула тебе нужна  Цитата(Pete @  7.1.2007,  23:04 ) Что значит «официальное»?  Это он о стандартных формулах комбинаторики! Цитата(Pete @  7.1.2007,  23:04 ) Смотри: у нас есть 5 позиций и 5 цифр. На 1-ю позицию можно поставить любую из этих 5-ти (5 вариантов), после чего останется уже 4 цифры и 4 свободные позиции. На 2-ю позицию можно поставить любую из 4-х оставшихся (4 варианта), причем независимо от 1-ой позиции. ... На 1-ю позицию можно поставить только 1-ну оставшуюся цифру, то есть только одним единственным способом. Так как постановки на каждую позицию независимы друг от друга, мы (по теореме умножения) перемножаем получившиеся количества вариантов: P = 5*4*3*2*1 = 5! = 120. Не повторяйся, я это ему уже писал  Цитата(apook @  7.1.2007,  18:20 ) Всвязи с этим может кому-то нечего делать(как мне)попробуйте решить ету задачю другим путем Зачем все усложнять, если чисто логически подумать можно намутить еще формулы, но мне кажется, что проще этой формулы A = n! нету ! Не зря же стока ученых математиков бились над этими формулами, и вывели свой стандарт   Ой чето меня на лирику потянуло

Автор: apook 7.1.2007, 16:40

Я в комбинаторике болван а обьяснить я попыцтался в присоединенном файле Цитата Только вот как ты это объяснять собираешься, и что такое x??..  ну не так уж прямо серьезно x это переменная

Автор: Pete 7.1.2007, 20:46

Цитата(AlexArs @  7.1.2007,  17:38 ) я это ему уже писал Написал, только зачем-то усложнил это расстановками. Ты же не будешь доказывать, что предел  Код            log(n)    lim     ------ = 0 n -> infty   n по правилу Лопиталя-Бернулли?    Цитата(apook @  7.1.2007,  17:40 ) x это переменная Как говорил один мой препод, «хоть горшком назови, главное определи, что такое горшок»... Что в твоем случае хранит x?

Автор: Sunvas 7.1.2007, 20:53

Я на Делфи уже все реализовал. Остается что-бы кто-то проконвертировал в С++ http://forum.vingrad.ru/index.php?showtopic=113874&view=findpost&p=883003

Автор: Pete 7.1.2007, 21:10

А зачем здесь программа? Для вычисления n! ?

Автор: Sunvas 7.1.2007, 21:11

Цитата(Pete @  7.1.2007,  21:10 ) А зачем здесь программа? Для вычисления n! ?   Для получения результата

Автор: Pete 7.1.2007, 21:15

Цитата(Sunvas @  7.1.2007,  22:11 ) Для получения результата Какого? Как именно она будет вычислять?

Автор: Sunvas 7.1.2007, 22:35

Цитата(Pete @  7.1.2007,  21:15 ) Какого? Если есть символы 1 2 3 4 5, то программа может посторить из них все возможные числа от 12345 до 54321. Цитата(Pete @  7.1.2007,  21:15 ) Как именно она будет вычислять? Алгоритм мой. Опен сорц

Автор: apook 8.1.2007, 05:46

Алгоритм у тебя конечно Опен Сорц и это хорошо но вот сложноват он в плане реализации на каком-либо языке пр.( чем меньше строчек тем лучше )  для нача ла надо было наверно на Pascale написать тем более для учебных целей Код на чистом Cи для подсчета неповторяющихся комбинаций из любого сочетания  неповторяющихся цифр Код #include "stdio.h" #include "stdlib.h" #include "conio.h" void main( int argc, char *argv[] ) { int i, j, x; long double *number, a=13/*сколько цифр в числе которое обрабатываем*/; number =( long double * ) malloc ( (a+1)*sizeof(long double) ); /* ********** */ printf( "Обработаем число "); for( i=0; i <a; i++ ) {     number[i] =i; //забиваем цмфрами     printf( "%d", i );     } printf( "\nКолмчество комбинаций без повторений " ); for( i=0; i <a-1; i++ ); //сколько цифр не считая первое for( j=1, x=1; j <=i; j++ ) //подсчет повторений первой цифры      x=x*j; x=x*a; //умножение этого числа на общее количество цифр  /* ********** */ printf( "%d\n", x ); getch(); return; }

Автор: Sunvas 8.1.2007, 15:25

Цитата(apook @  8.1.2007,  05:46 ) Алгоритм у тебя конечно Опен Сорц и это хорошо но вот сложноват он в плане реализации на каком-либо языке пр. Моей задачей было написать функции для комбинаторики. (всех ее типов сочетание, размещение, перестановки. Как с повтором так и без). Код и так меньше не придумаешь. Возможно несколько сложн для воспринимания, зато работает безотказно.

Автор: Pete 8.1.2007, 16:21

Цитата(Sunvas @  7.1.2007,  23:35 ) Если есть символы 1 2 3 4 5, то программа может посторить из них все возможные числа от 12345 до 54321. Извини, это уже другая задача. Спрашивалось вот что: Цитата(apook @  7.1.2007,  04:45 ) даны числа 12345 найти количество комбинаций разных которые можно составить из этих чисел чтоб все цифры присутствовали Хотя на русский это переводится с трудом, словосочетание «найти количество», вроде, не предполагает реализации алгоритма перебора, или печати, всех таких перестановок. Но с точки зрения программиста, реализованная тобой задача, конечно более интересна    Цитата(apook @  7.1.2007,  10:30 ) именно так выглядит изобретенный мной способ Так и не понял, какую задачу он решает и как работает...

Автор: apook 8.1.2007, 16:32

Цитата Так и не понял, какую задачу он решает и как работает... Я вот этого не понял Я создал этот топик и задача которую я решаю несколько другая чем была в тотраз Цитата найти количество комбинаций  количество комбинаций я как-раз и нахожу и не в лоб (перебором и т.п) а по некому алгоритму В будущем напишу с выводом всех комбинаций по этому-же алгоритму  а сейчас только подсчет всех возможных комбинаций причем начальное число можер быть любого вида 11258674445 или 4444444444444 и т.д тут лишка конечно дал!

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