Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 14.03.2009, 14:31
XTasy

 
Сообщений: n/a

Подскажите алгоритм
Добрый день. Задача следующая: нужно перебрать все возможные комбинации цифр последовательности (например, 211221) следующим образом:
цифры остаются на своих местах, но различаются комбинации тем,что браться может одна цифра,либо две.
Если непонятно изъясняюсь, вот:
2-11-22-1
21-1-2-21
21-12-2-1
и и т.д.
Заранее благодарен
  #2  
Старый 14.03.2009, 16:09
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Проще всего сгенерировать такие комбинации рекурсивно.
на каждом уровне рекурсии вставляем тире после первого символа текущего остатка строки, или после второго, и вызываем рекурсивную процедуру для каждого из вариантов остатка строки.

Другой путь:
Пусть в последовательности N символов, тогда между ними N-1 мест для вставки тире.
Пусть N-1 - битовое число - маска тире такая, что единичный бит означает наличие тире, а нулевой - отсутствие (например, все единичные биты - 2-1-1-2-2-1). Всего таких чисел 2^(N-1), однако нам нужны только такие двоичные числа, в которых не более одного нуля подряд.
  #3  
Старый 14.03.2009, 16:18
XTasy

 
Сообщений: n/a

большое спасибо
  #4  
Старый 14.03.2009, 17:15
XTasy

 
Сообщений: n/a

MBo, а не могли бы вы написать кусочек кода на паскале,демонстрирующий этот алгоритм (ваш первый сбособ)? а то у меня проблемы с рекурсией
  #5  
Старый 14.03.2009, 17:31
Новичок

Отправить личное сообщение для goong Посмотреть профиль Найти все сообщения от goong
 
Регистрация: 14.03.2009
Сообщений: 1

MBo,
ПРИВЕТ ДРУГАН, ТЫ УМЕЕШЬ ПОЛЬЗОВАТЬСЯ ПРОГРАММОЙ VISUAL BASIC 6.0 ????????
  #6  
Старый 14.03.2009, 17:44
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Код:
var
  s: string;

  procedure InsertIt(tail: string; Place: Integer);
  begin
    if Place < 1 then
      Memo1.Lines.Add(tail)
    else begin
      InsertIt(s[Place] + '-' + tail, Place - 1);
      if Place > 1 then
        InsertIt(s[Place - 1] + '-' + s[Place] + tail, Place - 2)
      else
        InsertIt(s[Place] + tail, Place - 2)
    end;
  end;

begin
  s := 'ABCDE';
  InsertIt(s[Length(s)], Length(s) - 1);

вывод:
A-B-C-D-E
AB-C-D-E
A-BC-D-E
A-B-CD-E
AB-CD-E
A-B-C-DE
AB-C-DE
A-BC-DE
  #7  
Старый 14.03.2009, 17:46
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>УМЕЕШЬ ПОЛЬЗОВАТЬСЯ ПРОГРАММОЙ VISUAL BASIC

нет, VB не знаю
  #8  
Старый 14.03.2009, 18:17
XTasy

 
Сообщений: n/a

MBo, премного благодарен Все работает отлично)
  #9  
Старый 18.03.2009, 10:30
гость

 
Сообщений: n/a

MBo, а можете более подробно объяснить логику приведенного кода. мне подобное необходимо сделать, но что то я не очень разобрался в коде(( заранее спасибо.
  #10  
Старый 18.03.2009, 10:40
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

При первом вызове передается хвост - последний символ строки, и место для вставки тире - перед ним

В рекурсивной процедуре тире вставляется на указанное место, и на одно место левее, получается ветвление на строку с одиночным символом, и с двумя вместе.

Можно прогнать код в отладчике, следя за переменными.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
волновой алгоритм, подскажите как оптимизировать для задачи NewRon Реализация, исходники, языки 4 20.05.2009 19:03
Подскажите, может существует другой алгоритм определения ширины многоугольника ViniPuh Математические алгоритмы 2 18.02.2008 19:55
Подскажите алгоритм MSDN Вычислительная геометрия 2 10.12.2007 19:57
подскажите алгоритм Человекъ Математические алгоритмы 6 24.03.2007 22:24
подскажите алгоритм обхода препятствий на Vb 6.0 IgNik500 Оффтопик 0 11.12.2006 13:44