Анализ Паскаль-головоломки

Представляю итоги решения Паскаль-головоломки. Всего было прислано 15 вариантов решений. Каждое из этих решений основано на одной из 5-ти главных идей.

Первое корректное решение задачи принадлежит анонимному посетителю сайта (ник "Evg Shakal"). 

Лучшее решение принадлежит (в порядке поступления решений) Акатову А, Хандошко А., Головенько О.

Самым активным участником конкурса и главным генератором идей признан Акатов Алексей.

К сожалению, 1 курс (на который в основном и был ориентирован этот конкурс) был представлен только двоими - Стаценко Наташей и Адамсоном Андреем. 

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

Развёрнутые комментарии можно получить по ходу ходу дискуссии, на которую я вас всех и приглашаю.

================================

 7.12.12   

Вариант1. Алексей Акатов: // ИДЕЯ 1 (на мой взгляд, во всех представленных решениях самая удачная, но  автором надолго забытая)

Max := 0;

  for I := 1 to N do

  begin

    A[I] := Random (10000);

    Max := (Max + A[I] + Abs (Max - A[I])) div 2; 

  end; {for}

  WriteLn ('Max = ', Max);

 

Решение некорректно (В ЧЁМ?), т.к. не соответствует условию задачи .

7.12.12

 

Вариант2. Некто Evg Shakal – аноним: //ИДЕЯ 2

 

 

z := mas[1];
 for ForX := 2 to MasMax do 
 begin
  for ForY := MaxEl to mas[ForX] do MaxEl := mas[ForX];
 end;

 writeln('Massiv Max element = ', MaxEl);

 

Первое правильное (если не считать описки в первой строке) решение. Во внутреннем цикле, играющем роль IF – неэффективность (КАК ЕЁ УСТРАНИТЬ?)

 

 

7.12.12

Вариант 3. Адамсон Андрей //ИДЕЯ 2.

Решение практически идентично предыдущему.

 

 

7.12.12

 

Вариант4. Стаценко Наташа: //ИДЕЯ 2 (эффективная версия)

 

 

max := a[1]; imax := 1; c := 0;
  for i := 1 to (n - 1) do begin
    Inc(c);
    for j := max to a[c+1] do begin
      max := a[c+1];
      imax := c + 1;
      break
    end;
  end;
  Write('Max element ', max, ' stoit na ', imax, ' meste');

 

Лучшее из правильных реализаций ИДЕИ 2 (Появился break). Но без c лучше бы обойтись!

 

 

 

8.12.12

Вариант5. Алексей Акатов:  //ИДЕЯ 2 (в неэффективной версии)

 

Randomize;

  Max := 0;

  for I := 1 to N do

  begin

    A[I] := Random (10000);

    for J := Max to A[I] do Max := J;

  end; {for}

  WriteLn ('Max = ', Max);

 

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

 

Вариант6. Алексей Акатов:  // Новая ИДЕЯ 3

 

type TElem = 0..9999;

var A: array[1..N] of TElem;

    Temp: array[TElem] of Byte;

    I, J, Max: Integer;

begin

  Randomize;

  FillChar (Temp, SizeOf (Temp), 0);

  Max := 0;

  for I := 1 to N do

  begin

    A[I] := Random (High (TElem) + 1);

    Temp[A[I]] := 1;

  end; {for}

  for I := High (TElem) downto Low (TElem) do

    for J := 1 to Temp[I] do

    begin

      Max := I;

      goto Finish;

    end; {for}

  Finish:

  WriteLn ('Max = ', Max);

End.

 

Применена Идея метода  ЛИНЕЙНОЙ СОРТИРОВКИ, описанного на этом сайте (вот почему полезно изучать, казалось бы, «сторонние» алгоритмы и программы!). Но всё же, данное решение имеет ряд недостатков. Оно очень неэффективно по памяти (резерв массива для всех возможных зачений в типе), содержит вложенные циклы, использует экзотические для новичков языковые конструкции и даже (ЗАЧЕМ?) оператор goto !

 

 

8.12.12

Вариант 7. Головенько Оксана: //ИДЕЯ 2 (в неэффективной версии)

Повтор предыдущих Вариантов 2, 3.

 

 

9.12.09.

Вариант7. Алексей Акатов:  // Новая ИДЕЯ 4  (мне она совсем не нравится!)

 

 

Var I, Max: Integer;

    Temp1, Temp2: Real;

begin

  Randomize;

  Max := 1;

  for I := 1 to N do

  begin

    A[I] := Random (9999) + 1;

    Temp1 := Int (A[I] / (Max + 0.01));

    Temp2 := Int (Max / A[I]);

    Max := Round (Temp1 / (Temp1 + 0.01)) * A[I] + Round (Temp2 / (Temp2 + 0.01)) * Max;

  end; {for}

  WriteLn ('Max = ', Max);

 

Плохая идея – привлечь вещественную арифметику для решения целочисленной задачи. К тому же, сузили задачу до рассмотрения НАТУРАЛЬНЫХ (исключив уже и ноль!)

 

Вариант8. Multysh – аноним:// ИДЕЯ 5.

 

const

  ColOfNumbers = 100;

var

  MasOfNumbers                  : array [ 1 .. ColOfNumbers ] of Integer;

  Index,IndexOfMax,SecondIndex  : Word;

  MasOfFlag                     : array [ 1 .. ColOfNumbers ] of Boolean;

begin

  Randomize;   

  For Index := 1 to ColOfNumbers do begin

    MasOfNumbers [ Index ] := Random ( 10001 ) - 5000;

    MasOfFlag [ Index ] := False;

 

  end;

  IndexOfMax := 1;

  MasOfFlag [ 1 ] := True;

  For Index := 2 to ColOfNumbers do begin

    MasOfFlag [ Index ] := MasOfNumbers [ Index ] > MasOfNumbers [ IndexOfMax ];

    MasOfFlag [ IndexOfMax ] := MasOfNumbers [ Index ] < MasOfNumbers [ IndexOfMax ];

    For SecondIndex := IndexOfMax to Index-1 do begin

      IndexOfMax := IndexOfMax + ord ( MasOfFlag [ Index ] );

    end;

  end;

  Writeln ( MasOfNumbers [ IndexOfMax ] );

  ReadLn;

end.

 

Недостатки: неэффективность (память, время), логическая сложность для новичков

 

Акатов Алексей (ещё 2 сходных варианта)

 

 

Randomize;

  Max := -9999;

  for I := 1 to N do

  begin

    A[I] := Random (19999) - 9999;

    Temp := Int (A[I] - Max);

    Temp := Round (Sqrt (Sqr (Temp)) / (Temp + 0.01)) + 1;

    K := Round (Temp / (Temp + 0.01));

    Max := A[I] * K + Max * (1 - K);

    Write (A[I], #9);

  end; {for}

  WriteLn;

  WriteLn ('Max = ', Max);

  ReadLn;

 

Неэффективность из-за стндартн. ф-ций и вещ. арифм., логическое несовершенство.

Зато, наконец, рассмотрены и отрицательные!

 

+++++++++

 

  Randomize;

  Max := -9999;

  for I := 1 to N do

  begin

    A := Random (19999) - 9999;

    Temp := Int (A - Max);

    Temp := Abs (Temp) + Temp;

    K := Round (Temp / (Temp - 0.01));

    Max := A * K + Max * (1 - K);

    Write (A, #9);

  end; {for}

  WriteLn;

  WriteLn ('Max = ', Max);

 

Улучшили, казалось бы,  но закрались новые ошибки …

 

======================

 

Акатов Алексей: (последний вариант автора)  //лёгкая вариация ИДЕИ 1, но уже в корректной  реализации:

for I := 1 to N do

  begin

    A[I] := Random (19999) - 9999;

    Write (A[I], #9);

  end; {for}

 

  Max := A[1];

  for I := 2 to N do

    Inc (Max, (Abs (A[I] - Max) + A[I] - Max) div 2);

  WriteLn;

  WriteLn ('Max = ', Max);

 

УШЛИ, наконец, от плавающей точки и получили, кажется, то что надо.

 

==============================================================

11.12.12.

 

Хандошко Александра Алексеевна , Головенько Оксана (независимо, в 1 день, лучшим из всех приведённых выше способом, похожим на последний вариант Акатова): // ИДЕЯ 1

 

max:=a[1];
  for i:=1 to n do max:=max+((a[i]-max)+abs(a[i]-max))/2;
  write('Maximum:');
  writeln(max:10:0);

Замечание. Правда, приведённой выше реализации Оксаны присуща некоторая лог. некорректность и падение эффективности из-за  ничем не обусловленной здесь вещ. арифметики (числа-то целые!). Просто использовать нужно было div.

 

 

Сальников Игорь – студент 2-го курса:

Работа не была рассмотрена до конца из-за содержавшейся в ней довольно странной «функции»:

function Prov_2(r: integer ) : boolean;
 begin
 Write(r);
end;

=======================================

3.5
Your rating: Нет Average: 3.5 (2 votes)

Комментарии

Вариант1. Алексей Акатов: //

Вариант1. Алексей Акатов: // ИДЕЯ 1 (на мой взгляд, во всех представленных решениях самая удачная, но автором надолго забытая)
...
Решение некорректно (В ЧЁМ?), т.к. не соответствует условию задачи .

Я думаю, некорректность в том, что Max := 0. Но тут предполагалось, что Max есть минимальное из всех возможных значений, а т.к. случайные числа берутся положительные, то и минимальное из них есть 0. А сама идея (я так думал, главное это, а не то, какие в конкретном примере числа мы используем для демонстрации работы) корректно работает со всеми целыми числами. Идея эта следующая:
Max := (Max + A[I] + Abs (Max - A[I])) div 2;
Эта формула находит максимальное значение между Max и A[I].

Вариант5. Алексей Акатов: //ИДЕЯ 2 (в неэффективной версии)
...
Как и предыдущая вариант того же автора, программа содержит ошибку (вероятно, из-за невнимательности чтения условия)

Я бы поспорил на счет того, ошибка это или нет :) В задаче сказано: целые числа, но не определен их диапазон. В моем примере берутся случайные числа от 0 до 99999, которые, как и сказано в условии, являются целыми.
При желании диапазон можно распространить и на отрицательные, алгорит самого поиска максимума от этого не меняется.

Применена Идея метода ЛИНЕЙНОЙ СОРТИРОВКИ, описанного на этом сайте (вот почему полезно изучать, казалось бы, «сторонние» алгоритмы и программы!). Но всё же, данное решение имеет ряд недостатков. Оно очень неэффективно по памяти (резерв массива для всех возможных зачений в типе), содержит вложенные циклы, использует экзотические для новичков языковые конструкции и даже (ЗАЧЕМ?) оператор goto !

Данный вариант и не претендовал на оптимальность. Это был именно один из возможных вариантов решения.
Суть проста: отсортировать массив и выдать последний элемент. А линейная сортировка позволяет сортировать массивы без единого if.

Улучшили, казалось бы, но закрались новые ошибки …

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

Андрей Р. аватар

Наверное я опаздал, но вышлю

Наверное я опаздал, но вышлю свое решение, а точнее только функцию

  1. function max(a,b:integer):integer;
  2. var f:boolean;
  3.     i:integer;
  4. begin
  5.      f:=true;
  6.      for i:=a to b do begin
  7.            f:=false;
  8.            break;
  9.      end;
  10.      if f then max:=a else max:=b;
  11. end;

как я понял данное решение использует ИДЕЮ2

Замечание: строку с break можно удалить, если она не нравится

Так if нельзя было

Так if нельзя было использовать!

  Я бы поспорил на счет того,

 

Я бы поспорил на счет того, ошибка это или нет :)   ... пишет Акатов Алексей.

А я бы не спорил Smile. Считается общепринятым (и не только в математике!) множество целых отличать от множества натуральных чисел, что впрочем, не мешает каждому натуральному числу быть одновременно и целым.  Другое дело что диапазоны множества целых и натуральных чисел в физических машинных представлениях всегда ограничены, но, конечно, не до полного отождествления этих двух фундаментальных числовых множеств. Я привык (и требую этого от студентов!) быть в формулировках точным. 

  Max := (Max + A[I] + Abs

  Max := (Max + A[I] + Abs (Max - A[I])) div 2;

Интересная формула! Никогда не встречала

Сама идея решения задачи

Сама идея решения задачи верная. Другое дело, что массив заполняется случайными положительными целыми числами.

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

Вот, как бы можно было бы более точно сформулировать условие:

Написать Паскаль-программу поиска максимального элемента в
целочисленном 100-элементном массиве, заполненном случайными числами от -1000 до 1000, НЕ ПОЛЬЗУЯСЬ УСЛОВНЫМИ
ОПЕРАТОРАМИ (включая и Case-операторы), а из операторов цикла -
ИСПОЛЬЗУЯ ТОЛЬКО FOR.

Доказать ее корректность для

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

Max (A, B) = (A + B + Abs (A - B)) / 2

если A > B, то Max (A, B) = (A + B + A - B) / 2 = A

если A < B, то Max (A, B) = (A + B + B - A) / 2 = B

Действительно. Надо ее

Действительно. Надо ее запомнить Smile

Очень интересный вариант

Очень интересный вариант

Оригинально! Т. е. термины

Оригинально! Т. е. термины множество целых и множество натуральных Вы предлагаете изъять из лексикона программистов и в формулировку каждой задачи о множество целых,  вводить спецификацию точных границ. Как мне Вам объяснить, что конкретные границы рассматриваемого множества целых к предложенной мною задаче в МОЕЙ формулировке никакого отношения не имеют и никак не должны влиять на  алгоритм её решения.

Я не могу и не желаю переформулировать своё общее условие под Ваш частный пример и Ваше частное решение, годное только для натуральных чисел и подтверждённое Вашим же примером для натуральных чисел.

А по поводу того, что "Сама идея решения задачи верная", никто и не спорит. Ещё раз внимательно прочтите мой комментарий, где написано, что  ИДЕЯ 1 (а к ней пришли не только Вы), не просто верна, но и  лучшая, на мой взгляд, из всех Ваших идей, а вот решение - не корректно.

И уж если так всё сложно объяснить,  я просто укажу Вашу ошибку. Вы  неприменно пытались присвоить в качестве первого значения Мах, то, которое является НАИМЕНЬШИМ среди всех обрабатываемых. Напомню Вам первое (неопубликованное, т.к. Вы сами заметили в нём ошибку):

Randomize;
  Max := Low (Integer);
  for I := 1 to N do
  begin
    A[I] := Random (10000);
    Max := (Max + A[I] + Abs (Max - A[I])) div 2;
  end; {for}
  WriteLn ('Max = ', Max);

Здесь Вы поняли условие задачи как надо и решали задачу для целых (правда, пример, снова для натуральных). Но когда Max := Low (Integer); подвело, Вы выбрали новую точку опоры, в новом варианте присвоив Max := 0; и, соответственно, рассчитывая теперь только на натуральные.

А ведь всё, что требовалось (и как поступали другие) - это оператор Max := a[1]; к которому Вы, в конце концов, в последнем варианте и пришли.

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

 

А вот ещё идея:    ..... var

А вот ещё идея:

   .....

var b: array[boolean] оf TElem;

   .....

b[true]:=a[1];

for i:=2 to n do begin

       b[ a[i]>b[true] ]:=a[i];

End;

write(b[true]);

Согласен, по-моему, спор

Согласен, по-моему, спор получился ни о чём Undecided

Наиболее популярными

Наиболее популярными оказались ИДЕИ 1 и 2.

ИДЕЮ 1. разъяснил Акатов Алексей, а вот ИДЕЯ 2 в чистом виде состоит в следующем:

условный оператор if a>max then max:=a  заменяем на

for i:= max to a do begin

   max:=a; break

End;

Здесь эксплуатируется скрытая проверка условия выхода из цикла. Если max>a, то в цикл попросту не входим.

Кстати, с этим связан, например, запрет в условии задачи оператора while. Действительно, сходным с выше приведённой реализацией образом, при его наличии, можно было бы записать:

While a>max do begin

   max:=a; break

End;

Если вдаться в подробности

Если вдаться в подробности реализации конструкций Паскаля, то мы получим, что использование for содержит скрытое условие, даже использование модуля abs содержит в себе скрытое условие.

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

  1. program Max100;
  2. {$APPTYPE CONSOLE}
  3. const N = 100;
  4. var A: array[1..N] of Integer;
  5.     I, B, Max: Integer;
  6. begin
  7.   Randomize;
  8.   for I := 1 to N do
  9.   begin // Заполняем массив:
  10.     A[I] := Random (1998) - 999;
  11.     Write (A[I], #9);
  12.   end; {for}
  13.   WriteLn; WriteLn; // пустая строка
  14.   Max := A[1];
  15.   for I := 2 to N do
  16.   begin // Ищем максимум:
  17.     B := A[I];
  18.     asm
  19.       mov EAX, B
  20.       sub EAX, Max
  21.       mov EDX, EAX
  22.       sar EDX, 31
  23.       xor EAX, EDX
  24.       sub EAX, EDX
  25.       add EAX, B
  26.       add Max, EAX
  27.       sar MAX, 1
  28.     end; {asm}
  29.   end; {for}
  30.   WriteLn ('Max = ',Max);
  31.   ReadLn;
  32. end.

Если уж привязываться к

Если уж привязываться к конкретной разрядности (что с лог. точки зрения мне не нравится) и при этом, не выводить за рамки обсуждения 1 курс (на чём настаиваю), то можно предложить следующую низкоуровневую постановку задачи.

ТРЕНЕРОВОЧНО-ПОВТОРИТЕЛЬНОЕ ЗАДАНИЕ ДЛЯ 1-го КУРСА:

         В предположении, что a - целочисленный массив, с,d, Max -  целочисленные переменные, а разрядность представления целых в дополнительном коде - 32 бита, решить Паскаль-головоломку следующим способом: условный оператор if a[i]>Max then Max:=a[i] моделировать присваиванием Max:= d*a[i]+c*Max, где в зависимости от того, что больше, Max или а[i], одна из переменных d и с равна нулю, другая - единице. При этом, при формировании значений c и d использовать поразрядные логические операции над целыми (shr, or, not и т.п.).

Подобный принц был

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

На счёт возможности определения коэффициента k с применением только поразрядных логических операций, я не уверен. Хотя, всё может быть...

 (1 - k) - это так. Но

 (1 - k) - это так. Но давайте слово дадим и студентамUndecided.

Всё, молчу

Всё, молчу Sealed

Этот вариант тоже очень

Этот вариант тоже очень интересный

Андрей Р. аватар

Действительно. Виноват. Но

Действительно. Виноват.

Но В.Ш. уже ниже написал как это исправить!

Всё же реально решить задачу,

Всё же реально решить задачу, используя только логические побитовые операции и div.

Как именно, не покажу Tongue out

Думаю, и div не обязателен.

Думаю, и div не обязателен.

А for можно использовать? Что

А for можно использовать? Что можно?

Ну, for, согласно основному

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

От div, конечно, избавиться

От div, конечно, избавиться можно, т.к. там div 2 у меня делается. Но если заменить его на сдвиг вправо, то слева вдвинется 0 и потеряется знак. Поэтому исключение div'а потребует нескольких логических операций, что приведёт к разбуханию кода.

Ой, кстати, я делал не так:

Ой, кстати, я делал не так: A[I] * K + Max * (1 - K)

По сути, я через только логические операции выразил ту формулу с модулем, что приведена выше.

А найти K тоже, в принципе, можно, но нужно ли?

Давайте, всё же, послушаем

Давайте, всё же, послушаем студентов ...