Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Delphi: Для новичков > Комбинации чисел

Автор: Zorak 22.2.2010, 19:49

Всем доброго времени суток! Нужно решить задачу нахождения всех комбинаций чисел. нисмог додуматся.. очень надеюсь на вашу помощь. Суть вот в чем: Есть какоето число К=9 (константа). и есть некое число N, которое задается пользователем, например 2. (2<= N <=5). Ето значит что в комбинациях будут принимать участия цифры 1 и 2. Если N=4 то участие в комбинации принимают участие 1,2,3 и 4.
Нужно записать в массив все комбинации, например N=2, тогда комбинации будут:

Код


1 1 1 1 1 1 1 1 1         //<--- всего 9 позиций, так как К=9;
1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 2 
1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 2 
1 1 1 1 1 1 2 2 1 
1 1 1 1 1 1 2 2 2
..........
1 2 2 2 2 2 2 2 2        //<--- На етом стоп!;

Тоесть нужно сделать ВСЕ комбинации, когда на первом месте стоит 1.

Если например N = 3 то комбинации будут примерно такие:

Код


1 1 1 1 1 1 1 1 1        
1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 2 
1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 2 
1 1 1 1 1 1 2 2 1 
1 1 1 1 1 1 2 2 2
..........
1 2 2 2 2 2 2 2 2        
..........
1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 3 1
1 1 1 1 1 1 1 3 3 
.........
1 2 2 2 2 2 2 2 3
1 2 2 2 2 2 2 3 2 
1 2 2 2 2 2 2 3 3 
........
1 3 3 3 3 3 3 3 3    // <--- На етом стоп!

Если чегото не понятно то говорите, попытаюсь обьяснить более доступно.
P.S. З.Ы. Количество вариантов вычисляется за формулой: кол := N^(k-1);

Автор: DarkProg 23.2.2010, 00:13

Есть такая вещь называется Код Грея поищи в нете, и переложи для своих нужд, я уже делал так пару раз, здесь в общем изходя из того что ты предлагаешь именно код грея и прокатит, только додумай как его надо адаптировать smile

Автор: Qu1nt 23.2.2010, 00:35

http://ru.wikipedia.org/wiki/Размещения

Автор: profesiachuvak 23.2.2010, 20:26

Цитата(Zorak @ 22.2.2010, 19:49

)

1 2 2 2 2 2 2 2 2

Почему на этой строчке следует останавливаться? А если будут все двойки : 2 2 2 2 2 2 2 2 2 ? Ведь все единицы могут быть.

Скорее всего кол-во комбинаций вычисляется с помощью фор-лы для перестановок с повторениями то есть :

a1 повторяется a раз
а2 повторяется b раз и т.д.
=> Число размещений = (a + b + ... + )! / (a1 + a2 + ... an)! .

например число 2 повторяется 1 раз, затем число 2 повторяется 2 раза и т.д. => (1 + 2 + 3 ... + 8)! / (2+ 2 +... +)!

Автор: Zorak 27.2.2010, 17:54

Цитата(profesiachuvak @ 23.2.2010, 20:26)

Цитата(Zorak @ 22.2.2010, 19:49

)

1 2 2 2 2 2 2 2 2

По условиям задачи на первом месте не должно стоять ничего кроме 1 .=)
З.Ы. Колччество вариантов я сумел обчислить, я не додумался как ето реализовать в програмировании). Мне нужен код чтобы показывал кти комбинации...
З.Ы.Ы. Кодом додумался. Так как у нас К константа, я подумал,что можно сделать приблизительно вот так:

Код


for i1 := 1 to 1 do
  for i2 := 1 to n do
    for i3 := 1 to n do
      for i4 := 1 to n do
        for i5 := 1 to n do
          for i6 := 1 to n do
            for i7 := 1 to n do
              for i8 := 1 to n do
                for i9 := 1 to n do
                  for i10 := 1 to n do
                    write(i1,i2,i3,i4,i5,i6,i7,i8,i9,i10);

Немного не по профессиональному и по нубски, но другим вариантом никак не додумался)

Автор: Juice 20.3.2010, 16:20

Может выложишь всё задание полностью?
З.Ы. Мне кажется, что гуглить в сторону "исходник брутфорса" надо.