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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 18.03.2009, 16:52
Новичок

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

последовательности длины N из чисел 1,2..M на заданную сумму элементов строки
Уважаемые участники форума

Здесь, на Алголист, приводится программа распечатки всех
последовательностей длины N из 1,2...М:

program Sequences;
type Sequence=array [byte] of byte;
var M,N,i:byte;
X:Sequence;
Yes:boolean;
procedure Next(var X:Sequence;var Yes:boolean);
var i:byte;
begin
i:=N;
{поиск i}
while (i>0)and(X[i]=M) do begin X[i]:=1;dec(i) end;
if i>0 then begin inc(X[i]);Yes:=true end
else Yes:=false
end;
begin
write('M,N=');readln(M,N);
for i:=1 to N do X[i]:=1;
repeat
for i:=1 to N do write(X[i]);writeln;
Next(X,Yes)
until not Yes
end.


Нужно внести изменение в программу. Надо чтобы она
печатала не все строки, а только те, сумма значений элементов
которых равна заданному заранее постоянному числу. Т.е. все строки
по сумме значений элементов равны. Такая таблица получится меньше.
В общем, задача для специалистов.

Спасибо
  #2  
Старый 18.03.2009, 17:35
MBo MBo вне форума
Местный

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

Код:
  procedure Generate(N, M, Sum: Integer; s: string);
  var
    i: Integer;
  begin
    if N  = 0 then begin
      if Sum = 0 then
        Writeln(s)
    end else begin
      for i := 1 to Min(M, Sum) do
        Generate(N - 1, M, Sum - i, s + IntToStr(i));
    end;
  end;

begin
  Generate(4, 4, 6, '');

1113
1122
1131
1212
1221
1311
2112
2121
2211
3111
  #3  
Старый 19.03.2009, 10:35
Новичок

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

Уважаемый MBo

Простите, пожалуйста, мою некомпетентность. Я не программист, а
работать надо. Как применить Ваш код в программе, чтобы он работал?
Кроме того, Pascal пишет, что Min - неизвестный идентификатор.
Уж, пожалуйста, доведите Ваш код до работающей программы.

Спасибо
  #4  
Старый 19.03.2009, 11:03
MBo MBo вне форума
Местный

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

Да уж...

program XXX;
use Math;
приведенный код
end.

Math - дельфийский модуль. Если ТурбоПаскаль используется - то не помню, есть ли там Min. тогда суперфункцию надо в код добавить:

function Min(A, B: Integer): Integer;
begin
if A > B then
Min := B
else
Min := A;
end;

кроме того, видимо, понадобится ввод N, M, Sum.
  #5  
Старый 19.03.2009, 16:31
Новичок

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

Уважаемый МВо

Ввел кусочки Вашего кода в создаваемую программу. Ошибка
возникла в самом начале: crt Math; - expect begin. Я просто стер эту
строку. Программа прошла объявление функции Min, затем ее
исполнение и споткнулась на IntToStr - опять неизвестный
идентификатор. К чему излишне много символов (букв)? Нельзя ли
свести их к чему то общему?
Во вводной я привел пример программы, она работает в оболочке
ТР 7.1 и выдает строки, можете проверить. У меня остается просьба:
чуть-чуть изменить эту программу или выложить другую готовую чтобы
получать не все строки, а только все строки заданной суммы.
Повторюсь, я не программист и учиться мне поздно. Приходится
прибегать к программам как к средству. Или к помощи.

Спасибо
  #6  
Старый 19.03.2009, 16:42
MBo MBo вне форума
Местный

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

TP у меня не стоит, проверить не на чем

Код:
program xxx;

function Min(A, B: Integer): Integer;
begin
  if A > B then
    Min := B
  else
    Min := A;
end;

function IToStr(i: Integer): string;
var
  s: string;
begin
  Str(i, s);
  IToStr := s;
end;

procedure Generate(N, M, Sum: Integer; s: string);
var
  i: Integer;
begin
  if N = 0 then begin
    if Sum = 0 then
      Writeln(s)
  end
  else begin
    for i := 1 to Min(M, Sum) do
      Generate(N - 1, M, Sum - i, s + IToStr(i) + ' ');
  end;
end;
var
  N, M, Sum: Integer;
begin
  Write('Numbers, MaxNumber, Sum =');
  Readln(N, M, Sum);
  Generate(N, M, Sum, '');
  Readln;
end.
  #7  
Старый 19.03.2009, 18:42
Новичок

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

Уважаемый МВо

Огромное Вам спасибо.

Ваша программа отлично работает.

Надеюсь и в дальнейшем пользоваться благорасположением и
опираться на помощь на Вашем форуме.

Спасибо
  #8  
Старый 20.03.2009, 13:19
Новичок

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

Здравствуйте, уважаемый МВо, здравствуйте, уважаемый форум

Обращаюсь к Вам с просьбой о дальнейшей помощи.

Уважаемый МВо, я о программе, которую Вы благосклонно
представили. Нельзя ли внести в нее дальнейшие изменения?
Отвлечемся немного в сторону. Если нанизать на кольцо нумерованные
шары, невозможно будет сказать, какой из них первый. Разве что
договориться. В производимой программой массе текста среди прочих
строк будут попадаться, к примеру, такие:
...
1 3 1 1 5 5 1
...
3 1 1 5 5 1 1
...
1 1 5 5 1 1 3
...
1 5 5 1 1 3 1
...
5 5 1 1 3 1 1
...
5 1 1 3 1 1 5
...
1 1 3 1 1 5 5
...
Но ведь это кольцо. А у кольца начала нет, и... Задача
программе будет: напечатать одного представителя кольца, а всех
остальных удалить. В первой строке самый первый символ
переставляется в конец строки, вся строка сдвигается влево и
сравнивается со всеми строками всей таблицы. При выявлении в
толще таблицы двойника, найденный второй убивается.
Программа возвращается к первой строке, теперь уже второй
символ переносится в конец строки, сдвиг и все по новой. И так по
очереди с третьим, четвертым и т. д. символами. Повторить столько
раз сколько имеется столбцов минус единица. Можно начать и с конца
строки. Сама таблица тоже сократится во столько раз сколько имеется
столбцов. Задача постоянства суммы значений (буде
математических) элементов строки также остается в силе.
И будет программа вывода последовательностей с
постоянной суммой строк и представлением единичных
представителей колец чисел. Так приблизительно
представляется.

Спасибо
  #9  
Старый 20.03.2009, 16:19
MBo MBo вне форума
Местный

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

То, что вам нужно, эквивалентно комбинаторной структуре
бинарные ожерелья (necklace) длиной (Sum - 1) с фиксированным числом нулей, да еще с дополнительным условием - не более M нулей подряд. Генерировать их напрямую, похоже, непросто. Если числа невелики, то проще генерировать какие-то более простые структуры с избытком, и отбирать нужные.
  #10  
Старый 20.03.2009, 22:18
Новичок

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

строки постоянной суммы как единичные представители колец чисел
Эти множества представляют собой собой композиции числа
заданной длины. Правда, это еще надо доказать. Доказательством
будет верность утверждения, что множество, получаемое при
пересечении множеств с разными ограничивающими условиями и
множество, получаемое программой хотя бы равны, пусть и не
тождественны. Т. е. данные не теряются. Эмпирика говорит, что это так,
но, вот, доказательства, увы...
То что здесь решается задачка об ожерельях, ну что же, пусть и
здесь прибавится. Тут вам и фильтрация, и отбор, и накладывание
дополнительных условий. О трудности задачи, - я не знаю. Но,
думается мне, такого профессионала как Вы только трудные задачи
достойны. Если это вершина, надо ее взять, чтобы идти выше. Если
этого доныне никто не делал, надо сделать. Учитывая ресурсозатраты,
понятное дело, приходится снижать планку запросов, положим, число
столбцов до 10, MaxNumber до 50, Sum до 50. Возможны варианты:
уменьшать одно, имея ввиду увеличение другого.
Надеюсь на участие сообщества форума.

Спасибо
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вычислить прямую, проходящую через заданную точку гость Вычислительная геометрия 10 13.03.2009 17:33
С++. Самоорганизующиеся последовательности данных гость Реализация, исходники, языки 3 28.12.2008 18:12
Вывод пути через матрицу последовательности узлов Алгоритм Флойда Cerberus Реализация, исходники, языки 1 18.11.2008 16:53
Оптимальное разбиение числа на сумму кубов Belyaev_Igor Математические алгоритмы (другое) 5 06.02.2008 00:45
Поиск последовательности xz121 Задачи 2 28.12.2007 13:15