Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Комбинаторика / 17 сообщений из 17, страница 1 из 1
27.09.2006, 17:55
    #34016752
VladBD
VladBD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
Какой здесь алгоритм?

есть числа 1,2,3,4,5,6,7
нужно сгенерить комбинации чисел (неодинаковых и неповторяющихся, т.е. перестановка не нужна) длиной 4 числа.

например
1234
1235
1236
1237
1245
..
..
4567

для самопроверки
По комбинаторике кол-во комб=35 для этого случая

Просто потом нужно будет сгенерить из 300 чисел комбинации длиной в 100 чисел...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2006, 18:36
    #34016907
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
VladBDПросто потом нужно будет сгенерить из 300 чисел комбинации длиной в 100 чисел...ВСЕ комбинации?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2006, 18:54
    #34016963
VladBD
VladBD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
да. но я думаю - предоставив начальству кол-во комбинаций и время на обработку - они снизят требования - но все равно комбинации надо будет делать
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2006, 19:13
    #34017015
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
VladBDда. но я думаю - предоставив начальству кол-во комбинаций и время на обработку - они снизят требования - но все равно комбинации надо будет делатьнасчет всех я сильно сомневаюсь... слишком много получается...

кстати, а почему 4 из 7 у вас 35 вариантов?
я бы сказал, что их 7*6*5*4=840
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2006, 20:09
    #34017092
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
VladBD Какой здесь алгоритм?
Напоминает циклическое добавление единицы в соответствующей системе счисления. Представьте себе, что Вы стартуете с числа 1234 и прибавляете по единице, только соблюдаете правило "каждая цифра больше предыдущей". То есть:

- стартуете с 1234
- добегаете до 1237
- прибавляете единицу, получаете 1245 [5 - минимальная цифра больше 4, пишем ее вместо нуля]
- добегаете до 1247, переключаетесь на 1256
...
- добегаете до 1267, переключаетесь на 1345
...

miksoftкстати, а почему 4 из 7 у вас 35 вариантов?
я бы сказал, что их 7*6*5*4=840
А я бы сказал, таки 35...... Если не верите биному, давайте так: ниже я называю 35, а оставшиеся 805 пожалуйста приведите Вы.

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
1345
1346
1347
1356
1357
1367
1456
1457
1467
1567
2345
2346
2347
2356
2357
2367
2456
2457
2467
2567
3456
3457
3467
3567
4567
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2006, 20:19
    #34017110
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
softwarerдавайте так: ниже я называю 35, а оставшиеся 805 пожалуйста приведите Вы.А чем плоха комбинация 4321? я не вижу условия у автора, что в комбинации числа должны быть строго в том же порядке, что и в исходном множестве. Кстати, так же не вижу утверждения, что это множество обязательно упорядочено.
И, опять же, не вижу как из "неодинаковых и неповторяющихся" следует "перестановка не нужна".

Но настаивать не буду... возможно, я просто забыл комбинаторику...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2006, 20:49
    #34017172
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
miksoftА чем плоха комбинация 4321?
Ничем не плоха. Ее можно включить, если выкинем 1234.

miksoftя не вижу условия у автора, что в комбинации числа должны быть строго в том же порядке, что и в исходном множестве.
Я вижу условие, что ему не нужны перестановки. То есть слово "комбинация" следует понимать как "множество", а не как "кортеж".

miksoftИ, опять же, не вижу как из "неодинаковых и неповторяющихся" следует "перестановка не нужна".
Каким бы образом оно ни следовало, оно явно и недвусмысленно указано как условие задачи.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 10:39
    #34017924
VladBD
VladBD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
Все правильно - вариантов 35 - перестановки не нужны.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 10:41
    #34017932
VladBD
VladBD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
softwarerНапоминает циклическое добавление единицы в соответствующей системе счисления.
Счас попробую накидать prg-шник
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 11:50
    #34018273
Андрей Спильный
Андрей Спильный
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
[quot VladBD]Какой здесь алгоритм?
quot]
эээ...рекурсивный спуск?
вы же сами, приведя 35 вариантов, следовали этому?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 12:08
    #34018355
VladBD
VladBD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
Все - всем спасибо - заработало!
Реально рекурсией двигаешься слева направо прибавляя разряды...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 12:09
    #34018364
Андрей Спильный
Андрей Спильный
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
эээ...а ведь можно и так наверно?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
program Project2;

uses SysUtils;

var
  a, b, c, d: integer;
begin
  for a :=  1  to  7  do
    for b := a+ 1  to  7  do
      for c := b+ 1  to  7  do
        for d := c+ 1  to  7  do
          writeln(IntToStr(a)+IntToStr(b)+IntToStr(c)+IntToStr(d));

  Readln;
end.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 12:21
    #34018418
VladBD
VladBD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
Все так - только если из 100 чисел комбинации делать - то код большой получится.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 12:30
    #34018466
VladBD
VladBD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
Все так - только если из 100 чисел комбинации делать - то код большой получится.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 12:37
    #34018501
Андрей Спильный
Андрей Спильный
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
VladBDВсе так - только если из 100 чисел комбинации делать - то код большой получится.
гы, а что, переписать с рекурсией нельзя?
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
program Project2;

uses SysUtils;

const
  max =  7 ;
var
  arr: array [ 0 .. 3 ] of integer;

  procedure PrintElement;
  begin
    Writeln(IntToStr(arr[ 0 ]* 1000 +arr[ 1 ]* 100 +arr[ 2 ]* 10 +arr[ 3 ]));
  end;

  procedure proc(level, start:integer);
  var
    loop:integer;
  begin
    for loop := start to max do
      begin
        arr[level]:= loop;
        if level< 3  then
          proc(level+ 1 ,loop+ 1 )
        else
          PrintElement;
      end;
  end;

begin
  proc( 0 , 1 );
  Readln;
end.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 12:39
    #34018512
Андрей Спильный
Андрей Спильный
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
просто когда я немного выше говорил о рекурсии, подразумевал немного другой алгоритм, с извлечением из набора элементов "уже использованный"
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2006, 13:33
    #34018769
VladBD
VladBD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Комбинаторика
у меня немного хуже код получился
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
const
  S = '1234567890';
  maxN =  10 ;
  minN =  2 ;

var
  Form1: TForm1;
  A : array[ 1 ..minN] of Integer;
  F1 : TextFile;

procedure TForm1.Button1Click(Sender: TObject);
var
  I, J, N : Integer;
begin
  for I :=  1  to minN do a[I] := I;
  AssignFile(F1, 'D:\test.txt');
  Rewrite(F1);
  GGG;
  CloseFile(F1);
  showmessage('yes');
end;

procedure GGG;
var
  SSS : String;
  I, J : Integer;
  Flag : Boolean;
begin
  SSS := '';
  for I :=  1  to minN do SSS := SSS+S[a[I]];
  Writeln(F1, SSS);

  //проверка на конец перебора
  Flag := True; for I :=  1  to minN do if a[I]<>maxN-minN+I then Flag := False; if Flag = True then Exit;

  for I := minN downto  1  do
  begin
    if a[I]+ 1 <=maxN-(minN-I) then
    begin
      a[I] := a[I]+ 1 ;
      for J := I+ 1  to minN do a[J]:=a[I]+J-I;
      Break;
    end;
  end;
  GGG;
end;

end.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Комбинаторика / 17 сообщений из 17, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]