На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Текст на заборе.
    Что-то никак не пойму, как это решается? Поэтому приведу текст задачи полностью.
    Цитата
    Мэр города Речуйска распорядился штрафовать за употребление нежелательных слов и обнародовал список этих слов с размером штрафа за каждое. Все эти слова состоят из букв "I", "N", "W".

    Некто строит незамкнутый забор длиной N досок. Имеются доски, на каждой из которых написана одна из букв "I", "N" или "W". Получившийся забор будет содержать надпись из вышеназванных букв. За каждое нежелательное слово, образуемое какими-либо последовательно стоящими буквами (при прочтении слева направо), придется заплатить штраф, причем столько раз, сколько раз оно встречается на заборе.

    Например, если запрещенными словами являются IN - штраф 1 рубль и WIWI - штраф 100 рублей, то за построение забора WIWIWINI будет назначен штраф 201 рубль.

    Требуется написать программу определения такой последовательности досок в заборе, для которой штраф минимален.

    Ограничения
    Штрафы выражаются в рублях Речуйска и представляются целыми числами от 1 до 100.
    Количество запрещенных слов <= 50.
    Длины запрещенных слов <= 6 символов.

    Входные данные
    Первая строка файла входных данных INPUT.TXT содержит длину забора N, вторая - количество слов в списке мэра M. В каждой из последующих M строк записано нежелательное слово и через пробел - соответствующий штраф. Все слова попарно различны, состоят только из больших букв латинского алфавита "I", "N" или "W".

    Входные данные корректны.

    Выходные данные
    Результат работы программы выводится в файл OUTPUT.TXT. Первая строка выходного файла должна содержать значение минимального штрафа, а вторая - последовательность из N букв, задающую один из возможных способов построения забора с минимальным штрафом.
    Пример:
    Цитата

    [Входные данные]
    8
    8
    W 10
    I 10
    N 30
    WI 1
    WW 10
    II 11
    WIW 2
    IWI 3


    [Результат]
    98
    IWIWIWIW
    Честно, кроме полного перебора ничего не придумал :(
       Первое, что заметил, это неправильная постановка задачи.
       Необходимо указать количества досок с каждой буквой. А то ответ напрашивается сам собой - взять буквы из слова за которое дается наименьший штраф!!!
        Не совсем! Более дорогое слово может состоять из нескольких "самых дешевых".
        Алгоритм решения очень прост, поэтому подсказывать не буду: думайте сами. ;D
          Найти наименьшее общее кратное длинн слов, расширить все слова путем их повторения, посчитать штрафы новых слов, и взять из слова, с наименьшим штрафом, нужное кол-во букв? Больше ничего не придумал.
          Блин, ну я и тупой.
            насколько я помню задача динамического програмирования
              После полного перебора самое простое решение:
              инициализируем одной буквой весь забор, считаем полную стоимость, принимаем ее за минимальную.
              Ставим указатель на последнюю доску и входим в цикл.
              1) Проверяем последня ли доска, если последняя, то сравнение штрафов и в случае успеха сохранение нового рекорда.
              2) Текущая цена больше минимальной? Да, то пункт (4)
              3) Доставляем доску после указателя, если забор не кончился, добавляем цену с учетом штрафов порожденных ей и перемещаем  указатель. В случае добавления прыгаем в пункт (2)
              4) Меняем доску под указаетлем если можем, сначала отнимаем штрафы порожденные предыдущей и ставим новую заместо нее и штрафы опять прибавляем. В случае смены прыгаем в пункт (2)
              5) Убираем доску под указаетлем, снимаем штрафы, перемещаем указатель к началу на одну позицию. Если убрали первую доску в заборе, то конец, иначе прыгаем в пункт (4)

              Задача похожа на задачу с коробкой, в которую надо положить предметы разного объема и веса, при этом добиться максимального веса при условии, что все предметы не помещаются в объем коробки.

              Более элегантного решения не знаю.
                Что-то в голову пришло, написал такую программу. Интересно, она работает?
                ExpandedWrap disabled
                  uses crt;
                  var n,m:byte;
                      sl:array[1..100]of string[6];
                      sl2:array[1..100]of string;
                      sh,sh2:array[1..100]of word;
                      res,res2:string;
                      i:word;
                      c:char;
                      k:set of char;
                      nk:word;
                      minn,min,sht:word;
                  function nod(a,b:longint):longint;
                   var p1,p2,p3:longint;
                   begin
                   if a>b then
                    begin p1:=a;p2:=b end
                     else
                    begin p1:=b;p2:=a end;
                   while p2<>0 do
                    begin
                    p3:=p1 mod p2;
                    p1:=p2;p2:=p3;
                    end;
                   nod:=p1;
                   end;
                  function nok(a,b:longint):longint;
                   begin
                   nok:=a*b div nod(a,b);
                   end;
                  function get(const s:string):word;
                   var a,z,r:word;
                   begin
                   r:=0;
                   for a:=1 to m do
                    for z:=1 to length(s)-length(sl[a])+1 do
                     begin
                     if copy(s,z,length(sl[a]))=sl[a] then
                      inc(r,sh[a]);
                     end;
                   get:=r;
                   end;
                  procedure buildres(num:byte);
                   var m:byte;
                   begin
                   res:='';
                   m:=1;
                   while length(res)<n do
                    begin
                    res:=res+sl2[num][m];
                    m:=1+(m mod length(sl2[num]));
                    end;
                   end;
                  begin
                  clrscr;
                  fillchar(sl,sizeof(sl),0);
                  writeln('‚ўҐ¤ЁвҐ ¤«Ё­­г § Ў®а ');
                  readln(n);
                  writeln('‚ўҐ¤ЁвҐ зЁб«® б«®ў');
                  readln(m);
                  writeln('‚ўҐ¤ЁвҐ б«®ў  Ё ива дл');
                  k:=[];
                  for i:=1 to m do
                   begin
                   read(c);
                   while c<>' ' do
                    begin
                    sl[i]:=sl[i]+upcase(c);
                    read(c);
                    end;
                   readln(sh[i]);
                   if length(sl[i])=1 then include(k,sl[i][1]);
                   end;
                  if not('I' in k) then begin inc(m);sl[m]:='I';sh[m]:=0;end;
                  if not('N' in k) then begin inc(m);sl[m]:='N';sh[m]:=0;end;
                  if not('W' in k) then begin inc(m);sl[m]:='W';sh[m]:=0;end;
                  nk:=nok(length(sl[1]),length(sl[2]));
                  for i:=3 to m do
                   nk:=nok(length(sl[i]),nk);
                  for i:=1 to m do
                   begin
                   sl2[i]:='';
                   while length(sl2[i])<nk do
                    sl2[i]:=sl2[i]+sl[i];
                   sh2[i]:=get(sl2[i]);
                   end;
                  minn:=1;buildres(1);min:=get(res);
                  for i:=2 to m do
                   begin
                   buildres(i);
                   sht:=get(res);
                   if sht<min then
                    begin
                    minn:=i;
                    min:=sht;
                    end;
                   end;
                  buildres(minn);
                  res2:=res+res;
                  min:=get(copy(res2,1,n));sht:=1;
                  for i:=2 to length(res2)-n+1 do
                   if get(copy(res2,i,n))<min then
                    begin sht:=i;min:=get(copy(res2,i,n))end;
                   
                  writeln('ЊЁ­Ё¬ «м­л© ива д: ',get(copy(res2,sht,n)));
                  writeln('ЏаЁ¬Ґа: ',copy(res2,sht,n));
                  readkey;
                  end.
                  2albom

                  работает она или нет, надо спрашивать у паскаля. ты бы написал, в чём заключается алгоритм и в чём его отличие от перебора, а то прислал здоровый кусок кода и радуется 8D
                    Цитата wormball, 21.03.03, 18:30:18
                    2albom

                    работает она или нет, надо спрашивать у паскаля. ты бы написал, в чём заключается алгоритм и в чём его отличие от перебора, а то прислал здоровый кусок кода и радуется 8D

                    тут даже и не кусок...
                      Да ну вас, грустно мне сегодня....

                      А пришло в голову то, что последовательность с наименьшим штрафом есть повторение некоторого слова, которое можно получить из исходных и некоторых других (если их нет в исходных). Потом мы расширяем все слова до нужной длинны (см вызов функции nok)и сравниваем их штрафы (их уже нужно считать самим). Ну и выбрав слово с наименьшим штрафом повторяем его n раз, и исчем в нем подстроку с минимальным штрафом. Она и есть ответ.
                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                      0 пользователей:


                      Рейтинг@Mail.ru
                      [ Script execution time: 0,0463 ]   [ 15 queries used ]   [ Generated: 4.03.24, 09:09 GMT ]