Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

Программирование с нуля - это совсем просто! 56) О лямзиках


Информационный Канал Subscribe.Ru

 
Школа программирования

Программирование с нуля - это совсем просто!

56) О лямзиках

Вот еще один вариант камень-ножницы-бумага - от Надежды:
http://russianenterprisesolutions.com/sbo/download/nad.rar

По поводу лямзиков, конечно самое красивое решение (рекурсивное) придумала Таня. По принципу - пусть работает железный человек :)

То есть компьютер. Зачем ему еще процесс решения объяснять? :) Пусть сам и думает.

Для наглядности я Танин код так переписал (некоторые использованные ей вещи мы не проходили, но не знаю правда, корректно получился мой вариант или нет -):

  program Project1;

  {$APPTYPE CONSOLE}

  uses
    SysUtils;

  var arr: array [1..3] of integer;
  i,red, green, blue,sum: integer;

  //рекурсивная процедура
  //в массиве arr считается сколько раз какая популяция останется
  //потом исходя из этих данных считается процент вроятности всех
  //возможных конечных цветов
  procedure RGB(r,g,b: integer);
  begin
   if (r>0) and (g=0) and (b=0) then arr[1]:=arr[1]+1; //красные
   if (r=0) and (g>0) and (b=0) then arr[2]:=arr[2]+1; //зеленые
   if (r=0) and (g=0) and (b>0) then arr[3]:=arr[3]+1; //голубые
  //если еще имеются лямзики более одного цвета, повторный вызов
  функций
  //в трех вариантах=)
   if ((r>0) and (g>0) and (b>0)) or ((r>0) and (g>0) and (b=0)) or
     ((r=0) and (g>0) and (b>0)) or ((r>0) and (g=0) and (b>0)) then
  begin
    RGB(r+1,g-1,b-1);
    RGB(r-1,g+1,b-1);
    RGB(r-1,g-1,b+1);
  end;
  end;

  begin

  for i:=1 to 3 do
  arr[i]:=0;

  write ( ' Enter RED: ' );
  readln(red);
  write ( ' Enter GREEN: ' );
  readln(green);
  write ( ' Enter BLUE: ' );
  readln (blue);

  RGB(red,green,blue); //вызов процедуры

  sum:=0;
  for i:=1 to 3 do
  sum:=sum+arr[i];

  //вывод процентного соотношения всех возможных вариантов
  цветов
  writeln ( ' RED ' ,arr[1]*100/sum:4:1, ' % ' );
  writeln ( ' GREEN ' ,arr[2]*100/sum:4:1, ' % ' );
  writeln ( ' BLUE ' ,arr[3]*100/sum:4:1, ' % ' );
  readln;
  end.

Функция RGB получает на вход некоторое число лямзиков, распределенное по цветам, и смотрит - если дальше можно себя не вызывать, а достигнута финальная позиция (лямзики только одного цвета), просто прекращаем спуск дальше, и возвращаемся обратно.

В противном случае надо посмотреть все три возможных пути развития - если спарить красный с зеленым, красный с синим, синий с зеленым. Правда, проверочное условие тут не совсем верно записано - может быть, что красных ноль, и все равно вызовется RGB, с числом красных равным -1 уже. Как то так наверно надо:

   if ((r>0) and (g>0) and (b>0)) or ((r>0) and (g>0) and (b=0)) then
       RGB(r-1,g-1,b+1);

   if ((r>0) and (g>0) and (b>0)) or ((r>0) and (g=0) and (b>0)) then
       RGB(r-1,g+1,b-1);

   if ((r>0) and (g>0) and (b>0)) or ((r=0) and (g>0) and (b>0)) then
       RGB(r+1,g-1,b-1);

Да, вот стал дальше письма смотреть - Таня потом тоже переделала :)

   //если имеются лямзики всех цветов
   if ((r>0) and (g>0) and (b>0)) then
   begin
     RGB(r+1,g-1,b-1,rez);
     RGB(r-1,g+1,b-1,rez);
     RGB(r-1,g-1,b+1,rez);
   end;
   //если только красные и зеленые
   if ((r>0) and (g>0) and (b=0)) then
    RGB(r-1, g-1, b+1, rez);
   //если только зеленые и голубые
   if ((r=0) and (g>0) and (b>0)) then
    RGB(r+1, g-1, b-1, rez);
   //если только красные и голубые
   if ((r>0) and (g=0) and (b>0)) then
    RGB(r-1, g+1, b-1, rez);

   end;

Неплохой вариант без рекурсии, отыскивающий хотя бы один правильный вариант (и работающий очень быстро!), предложила Надежда:

  type
    TForm1 = class(TForm)
      Button1: TButton;
      Edit1: TEdit;
      Edit2: TEdit;
      Edit3: TEdit;
      Label1: TLabel;
      Label2: TLabel;
      Label3: TLabel;
      ListBox1: TListBox;
      Button4: TButton;
      Button5: TButton;
      Label4: TLabel;
      Label5: TLabel;
      Label6: TLabel;
      Label7: TLabel;
      Label8: TLabel;
      Label9: TLabel;
      procedure Button1Click(Sender: TObject);
      procedure Button5Click(Sender: TObject);
      procedure Button4Click(Sender: TObject);
    private
      { private declarations }
    public
      { public declarations }
    end;

  var
    Form1: TForm1;
  const s1:String = ' Встреча красного и зеленого, получился голубой, ' ;
        s2= ' Встреча красного и голубого, получился зеленый, ' ;
        s3= ' Встреча зеленого и голубого, получился красный, ' ;
  implementation

  {$R *.dfm}
  procedure TForm1.Button1Click(Sender: TObject);
  var kr1,zel1,gol1,i,sch1,sch2,sch3,i1,i2,i3:Integer;
  sch:String;
  begin
  if (Edit1.Text= ' ' )or(Edit2.Text= ' ' )or(Edit3.Text= ' ' ) then exit;
  kr1:=StrToInt(Edit1.Text);
  zel1:=StrToInt(Edit2.Text);
  gol1:=StrToInt(Edit3.Text);
  if (kr1=0)or(zel1=0)or(gol1=0) then exit;
  //Имеется три направления поиска возможных вариантов встречи
  лямзиков
  //Первое направление от красных к голубым
  i:=0;
  while( (kr1<>0)and(zel1<>0))or((kr1<>0)and(gol1<>0))or((gol1<>0)and(zel1<>
  0))do //Делаем пока два цвета не
  begin //станут равны 0
  while( kr1>0)and(gol1>0) do
          begin
          kr1:=kr1-1;
          zel1:=zel1+1;
          gol1:=gol1-1;
  ListBox1.Items.Add(s1+ IntToStr(kr1)+ ' -красных,
  ' +IntToStr(zel1)+ ' -зеленых, ' +IntToStr(gol1)+ ' -голубых ' );
          i:=i+1;
          end;
  //После этого цикла остались либо красные и зеленые, либо
  голубые и зеленые, проверяем

  if (kr1>0)then //спариваем
     while (kr1>0)and(zel1>0) do // красных и зеленых или
          begin
          kr1:=kr1-1;
          zel1:=zel1-1;
          gol1:=gol1+1;
  ListBox1.Items.Add(s2+ IntToStr(kr1)+ ' -красных,
  ' +IntToStr(zel1)+ ' -зеленых, ' +IntToStr(gol1)+ ' -голубых ' );
          i:=i+1;
          end;
  if (gol1>0)then
           while( zel1>0)and(gol1>0)do //голубых и зеленых
           begin
           kr1:=kr1+1;
           zel1:=zel1-1;
           gol1:=gol1-1;
  ListBox1.Items.Add(s3+ IntToStr(kr1)+ ' -красных,
  ' +IntToStr(zel1)+ ' -зеленых, ' +IntToStr(gol1)+ ' -голубых ' );
           i:=i+1;
           end;
  end;
  ListBox1.Items.Add( ' ходов ' +IntToStr(i)+ ' I- вариант ' );
  //Результат запоминаем
  if kr1<>0 then sch1:=1
          else if zel1<>0 then sch1:=2
                  else sch1:=3;
  //
  kr1:=StrToInt(Edit1.Text);
  zel1:=StrToInt(Edit2.Text);
  gol1:=StrToInt(Edit3.Text);
  //Второе направление от красныx к зеленым
  i:=0;
  while( (kr1<>0)and(zel1<>0))or((kr1<>0)and(gol1<>0))or((gol1<>0)and(zel1<>
  0))do
  begin
  while (kr1>0)and(zel1>0)do
          begin
          kr1:=kr1-1;
          zel1:=zel1-1;
          gol1:=gol1+1;
  ListBox1.Items.Add(s3 + IntToStr(kr1)+ ' -красных,
  ' +IntToStr(zel1)+ ' -зеленых, ' +IntToStr(gol1)+ ' -голубых ' );
          i:=i+1;
          end;
  //После этого цикла остались либо красные и голубые, либо
  зеленые и голубые, проверяем
  if (zel1>0) then
          while( gol1>0)and(zel1>0)do
                  begin
                  kr1:=kr1+1;
                  zel1:=zel1-1;
                  gol1:=gol1-1;
  ListBox1.Items.Add(s1 + IntToStr(kr1)+ ' -красных,
  ' +IntToStr(zel1)+ ' -зеленых, ' +IntToStr(gol1)+ ' -голубых ' );
                  i:=i+1;
                  end;
  if (kr1>0)then
            while( gol1>0)and(kr1>0)do
                  begin
                  gol1:=gol1-1;
                  zel1:=zel1+1;
                  kr1:=kr1-1;
  ListBox1.Items.Add(s2 + IntToStr(kr1)+ ' -красных,
  ' +IntToStr(zel1)+ ' -зеленых, ' +IntToStr(gol1)+ ' -голубых ' );
                  i:=i+1;
                  end;
  end;
  ListBox1.Items.Add( ' ходов ' + IntToStr(i)+ ' II-вариант ' );
  //Результат запоминаем
  if kr1<>0 then sch2:=1
          else if zel1<>0 then sch2:=2
                  else sch2:=3;

  //
  kr1:=StrToInt(Edit1.Text);
  zel1:=StrToInt(Edit2.Text);
  gol1:=StrToInt(Edit3.Text);
  //Третье направление от зеленых к голубым
  i:=0;
  while( (kr1<>0)and(zel1<>0))or((kr1<>0)and(gol1<>0))or((gol1<>0)and(zel1<>
  0))do
  begin
  while (zel1>0)and(gol1>0)do
          begin
          kr1:=kr1+1;
          zel1:=zel1-1;
          gol1:=gol1-1;
  ListBox1.Items.Add(s2+ IntToStr(kr1)+ ' -красных,
  ' +IntToStr(zel1)+ ' -зеленых, ' +IntToStr(gol1)+ ' -голубых ' );
          i:=i+1;
          end;
  //Здесь остались либо зеленые и красные, либо голубые и красные
  if (gol1>0) then
        while( kr1>0)and(gol1>0)do
           begin
           kr1:=kr1-1;
           zel1:=zel1+1;
           gol1:=gol1-1;
  ListBox1.Items.Add(s3+ IntToStr(kr1)+ ' -красных,
  ' +IntToStr(zel1)+ ' -зеленых, ' +IntToStr(gol1)+ ' -голубых ' );
           i:=i+1;
           end;
  if (zel1>0)then
         while( kr1>0)and(zel1>0) do
           begin
           kr1:=kr1-1;
           zel1:=zel1-1;
           gol1:=gol1+1;
  ListBox1.Items.Add(s1+ IntToStr(kr1)+ ' -красных,
  ' +IntToStr(zel1)+ ' -зеленых, ' +IntToStr(gol1)+ ' -голубых ' );
           i:=i+1;
           end;
  end;
  ListBox1.Items.Add( ' ходов ' +IntToStr(i)+ ' III-вариант ' );
  //Запоминаем результат
  if kr1<>0 then sch3:=1
          else if zel1<>0 then sch3:=2
                  else sch3:=3;

  //Анализируем результаты-строку, в которой могут быть "1","2","3"

  sch:=IntToStr(sch1)+IntToStr(sch2)+IntToStr(sch3);
  //Анализируем данные, полученные в результате поиска по трем
  возможным направлениям
  //Подсчитываем наличие положительных результатов по тому или
  иному цвету и выдаем результат
  //Определяем наличие "1, 2, 3"
  i1:=0;
  i2:=0;
  i3:=0;
  for i:=1 to 3 do
          if sch[i]= ' 1 ' then i1:=i1+1
                  else if sch[i]= ' 2 ' then i2:=i2+1
                          else i3:=i3+1;
  //Выдаем результат
  if ((i1=0)and(i2=0)and(i3>0)) then Label4.Caption:=Label4.Caption+ ' только
  голубой '
   else if ((i1=0)and(i2>0)and(i3=0)) then Label4.Caption:=Label4.Caption+ '
  только зеленой '
   else if ((i1>0)and(i2=0)and(i3=0)) then Label4.Caption:=Label4.Caption+ '
  только красной '
   else if ((i1=0)and(i2>0)and(i3>0)) then Label4.Caption:=Label4.Caption+ '
  зеленой или голубой '
   else if ((i1>0)and(i2=0)and(i3>0)) then Label4.Caption:=Label4.Caption+ '
  красной или голубой '
   else if ((i1>0)and(i2>0)and(i3=0)) then Label4.Caption:=Label4.Caption+ '
  красной или зеленой '
   else if ((i1>0)and(i2>0)and(i3>0)) then Label4.Caption:=Label4.Caption+ '
  красной, голубой или зеленой ' ;
  end;

  procedure TForm1.Button5Click(Sender: TObject);

  begin
  ListBox1.Items.Clear;
  Edit1.Text:= ' ' ;
  Edit2.Text:= ' ' ;
  Edit3.Text:= ' ' ;
  Label4.Caption:= ' ' ;
  end;

  procedure TForm1.Button4Click(Sender: TObject);
  begin
  Close;
  end;

Что хорошо - работает молниеносно при большом числе лямзиков!!!

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

Недостаток рекурсии - что может считать долго, и хотя код программы короткий, придумать такую краткость тоже не всегда просто.

Вот например результат Тани:

к примеру по 7 лямзиков каждого цвета еще за одну секунду
по 8 - за 25 секунд (при этом перебирает около 7*10 в 8 степени конечных вариантов)
по 9 - уже 9 с половиной минут перебирал
запустила по 10 - не дождалась=)))

Хотя при известной практике перейти к рекурсивному мышлению не так сложно. Оно в первое время кажется необычным немного :)

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

Кроме того, существуют формальные алгоритмы разложения рекурсивной программы в линейную, с помощью циклов и массивов.
Правда, код получается ужасным :)

А Artsubscr сделал целую исследовательскую панель для анализа разных алгоритмов! Вот здесь:

http://russianenterprisesolutions.com/sbo/download/calc.rar

Интересный вариант, с графической визуализацией процесса стыковки лямзиков (не поймите неправильно :), придумал Алексей: http://russianenterprisesolutions.com/sbo/download/lz.rar

Решение на Си++ - Екатерины:
http://russianenterprisesolutions.com/sbo/download/cpp.zip.

Рекурсивный вариант Дмитрия: http://russianenterprisesolutions.com/sbo/download/dim.zip

Вот временная оценка Дмитрия:

15 лямзиков обсчитывает за 20 сек.,16 лямзиков за 2 мин., а 18 лямзиков ждал 25 мин.- не дождался(около 900000 вариантов было).

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

Как показать новое значение в поле немедленно? Если это сделать в процессе расчета, то скорее всего данные в поле перерисуются не сразу, а лишь по окончании всего процесса счета, что не позволяет следить за его динамикой. Как же быть? Воспользоваться методом Repaint.

Например:

  for i := 1 to 1000000000000 {условно} do
    begin
    x := sin(i);
    Label1.Caption := i;
    end;

В таком цикле скорее всего содержимое поля Label1, несмотря на то, что оно обновляется в цикле 1000000000000 раз, будет реально показано на экране обновленным лишь когда этот цикл, и включающий его обработчик (нажатия на кнопку например) закончится целиком, и управление будет передано Windows. Можно однако явно сказать Windows, что надо немедленно показать содержимое поля Label1:

  for i := 1 to 1000000000000 {условно} do
    begin
    x := sin(i);
    Label1.Caption := i;
    Label1.Repaint; // перерисовать немедленно!
    end;

Тогда в цикле содержимое поля-надписи будет перерисовано 1000000000000 раз. Что, с другой стороны, может привести к серьезной дополнительной нагрузке на процессор.

Я в таких случаях прикидываю, сколько времени будет считаться такой цикл (например, 360 секунд), и перерисовываю поле-надпись примерно раз в секунду:

  t := 1000000000000 div 360; // сколько проходов цикла на секунду -
  for i := 1 to 1000000000000 {условно} do
    begin
    x := sin(i);
    if (i mod t) = 0 then // примерно секунда прошла...
       begin
       Label1.Caption := i;
       Label1.Repaint; // перерисовать немедленно!
       end
    end;

Repaint - практически для всех элементов управления реализован - списков, редакторов, кнопок итд.


* Что такое WinApi?

Это программный интерфейс (API) к стандартным функциям Windows (Windows API, Win32 еще называют), как бы "встроенный" в сами Windows. На самом деле большинство компонентов Дельфи со своими свойствами и методами - это такая своеобразная настройка, оболочка, обертка над функциями WinApi, которые в лоб пользовать крайне неудобно. Первые программы для виндовс писались именно в соответствии с требованиями WinApi, и обычная небольшая, даже ничего не делающая программка занимала сотни строк кода, и при небольшой описке начинались странные глюки... Массовой такая технология конечно стать не могла. А с появлением визуальных сред разработки ситуация, как мы видим :) коренным образом изменилась.

* Каким образом сделать что бы при сохранении файла он имел иконку своего вида (как файлы Word или Corel DRAW) У меня сечас сохраняется с расширением txt (иконка "Блокнот"). Пробовал менять расширение - иконка получалась как "неопознанная программа". А как рисунок прицепить не нашел пути.

Иконку - это надо в виндовс добавлять ассоциацию с вашим расширением файла. Я делал когда-то, но вещь не совсем тривиальная. Вот здесь почитайте:

http://www.cracklab.ru/pro/faq.php?pg=307

С текстом - есть хороший компонент RichEdit на панели Win32, позволяет отображать форматированный текст, в rtf-формате. Отдельные слова выделять цветом и размером и тд.

* И еще про сохранение настройки программы. (запустил программу - настроил шрифт, цвет и т.п.) При следующем запуске надо делать все снова. Как то сохраняется у других программ.

Настройки программ - в момент закрытия (событие OnClose формы) пишите все параметры (размер и положение окна например) в какой-то свой файл, например текстовый settings.ini. А при запуске (OnCreate) - считываете и задаете нужные значения разным свойствам программно.

* В коде

  for i1:=1 to 100 do
           begin
           ...
           end;

  x[ i1 ] := xmin;

почему [Warning] Project23.dpr(29): FOR-Loop variable i1 may be undefined after loop

Да, это важная вещь, а я не объяснил. В Дельфи считается, что после выполнения цикла переменная-счетчик теряет значение. То есть по окончании цикла for значение переменной i1 будет не определено!


Сейчас я отвечаю на письма от 28 февраля. Это означает (некоторые не понимают, как ни удивительно :), что если вы писали 1 или 3 марта, то до вас еще очередь не дошла.

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

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

Один из хороших подходов - делать сложные, большие программы. То есть не сто простых, а десять сложных. А еще лучше - одну, но очень большую :) Определить сложность под себя можно так - прикинуть число строк (операторов) своей самой большой программы, программа объемом в 10 раз больше будет вашим текущим пределом. Наши примеры - до сотни строк, значит в тысячу строк следующий уровень будет. Типичные программы, сделанные умельцами в одиночку, на сайтах типа download.ru, где-то от 1 до 5 тысяч строк кода. 10 тысяч - это уже серьезно :) А например, самые крупные в мире программные проекты (сегодня это американские военные системы, управления спутниками, глобальной связи, бортовой софт истребителей итп) - десятки миллионов строк кода. До сотни миллионов операторов человечество еще по-моему не дошло :)

Предел одного человека - ну наверно проект в тысяч сто строк (операторов). В несколько тысяч раз сложнее лямзиков примерно :)


(c) 2004-2005 Сергей Бобровский bobrovsky@russianenterprisesolutions.com

Школа программирования с нуля
Все предыдущие выпуски базового курса тут:
http://russianenterprisesolutions.com/sbo/

 

http://subscribe.ru/
http://subscribe.ru/feedback/
Подписан адрес:
Код этой рассылки: comp.soft.prog.prognull
Отписаться

В избранное