Форум » Обработка числовых последовательностей » Оцените, пожалуйста, решение » Ответить

Оцените, пожалуйста, решение

Adapalen: Хочу пойти на апелляцию по поводу задания С1, но боюсь, что снизят баллы за С4. Проверьте, пожалуйста, решение и скажите, снизят ли балл за него или нет (Сейчас мне поставили 3). Условие примерно такое: На входе программа получает последовательность чисел (Например: 1 2 3 4 5 6 7 8 9) Пусть S - сумма квадратов чисел A и B (S = A^2 + B^2). Причем между A и B должно быть не меньше 4 чисел. Из примера выше числа A и B могут быть равны: 1 и 6, 1 и 7, 1 и 8, 1 и 9, 2 и 7, 2 и 8 и т.д. Нужно найти максимально возможное значение S для этой последовательности На вход программе в первой строчке подается число N - количество чисел (N>5) В следующих N строках записаны вещественные числа Пример input: 10 11 2.1 12 66 45 1 28 13 35 11 output для этого примера: 5581 Мой ответ: Описание программы: 1) Создаем массив, в котором будем хранить 6 чисел a = {0, 0, 0, 0, 0, 0); 2) Заполним его первыми пятью числами. Получим: a = {0, 10, 11, 2.1, 12, 66} 3) Получаем следующее число и ставим его в конец массива, но перед этим: 4) Проверяем a[0] > a[1], если это так, то a[0] сохраняем, а остальные сдвигаем влево на 1 позицию. Иначе все элементы сдвигаем влево, а первый удаляем Получим: a = {10, 11, 2.1, 12, 66, 45} (где 45 - полученное число) 5) Считаем (a[0])^2 + (a[5])^2. Если эта сумма больше той, которую получили на прошлых выполнениях цикла, то запоминаем ее. Повторяем действия 3,4,5 до тех пор, пока нам дают новые числа. В конце выводим полученную сумму. Она и будет наибольшей Массив a[] как бы "пробегает" по последовательности чисел, оставляя в первом элементе максимальное число, до которого "могут дотянуться" новые полученные числа. Исходный код на C++: [quote]#include <iostrem> int main() { int N; //тут будет храниться количество чисел std::cin>>N; double a[6]={0}, n, s=0; //s - переменная для суммы for(int i=1; i<=5; ++i) //заполняем массив первыми 5-ю числами { std::cin>>n; a=n; } N-=5; //Уменьшаем N, т.к. 5 чисел уже записали for(int i=0; i<N; ++i) { if(a[0] < a[1]) //Если первое больше второго, сохраняем первое a[0] = a[1]; a[1]=a[2]; a[2]=a[3]; a[3]=a[4]; a[4]=a[5]; //сдвигаем элементы a[5] = n; if(a[0]*a[0] + a[5]*a[5] > s) // проверяем сумму s = a[0]*a[0] + a[5]*a[5]; } std::cout<<s; return 0; }[/quote] В исходном коде нашел 1 грубую ошибку. Не считываю новые числа в переменную n во втором цикле for. Возможно, что работу оценивали по алгоритму на русском языке, либо просто пропустили ошибку. Иначе 3 балла бы не поставили.

Ответов - 14

SergJP: Коллеги, оцените наше решение 48-й задачи про Тетрис, которое мы с моим учеником Владом придумали вместе. Вот задание. 48) Соревнования по игре «Тетрис-онлайн» проводятся по следующим правилам. Каждый участник регистрируется на сайте игры под определённым игровым именем. Имена участников не повторяются. Чемпионат проводится в течение определённого времени. В любой момент этого времени любой зарегистрированный участник может зайти на сайт чемпионата и начать зачётную игру. По окончании игры её результат (количество набранных очков) фиксируется и заносится в протокол. Участники имеют право играть несколько раз. Количество попыток одного участника не ограничивается. Окончательный результат участника определяется по одной игре, лучшей для данного участника. Более высокое место в соревнованиях занимает участник, показавший лучший результат. При равенстве результатов более высокое место занимает участник, раньше показавший лучший результат. В ходе соревнований заполняется протокол, каждая строка которого описывает одну игру и содержит результат участника и его игровое имя. Протокол формируется в реальном времени по ходу проведения чемпионата, поэтому строки в нём расположены в порядке проведения игр: чем раньше встречается строка в протоколе, тем раньше закончилась соответствующая этой строке игра. Напишите эффективную, в том числе по памяти, программу, которая по данным протокола определяет победителя и призёров. Гарантируется, что в чемпионате участвует не менее трёх игроков. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Описание входных данных Первая строка содержит число N- общее количество строк протокола. Каждая из следующих N строк содержит записанные через пробел результат участника (целое неотрицательное число, не превышающее 100 миллионов) и игровое имя (имя не может содержать пробелов). Строки исходных данных соответствуют строкам протокола и расположены в том же порядке, что и в протоколе. Гарантируется, что количество участников соревнований не меньше 3. Описание выходных данных Программа должна вывести имена и результаты трёх лучших игроков по форме, приведённой ниже в примере. Пример входных данных: 9 69485 Jack 95715 qwerty 95715 Alex 83647 М 197128 qwerty 95715 Jack 93289 Alex 95715 Alex 95710 M Пример выходных данных для приведённого выше примера входных данных: 1 место. qwerty (197128) 2 место. Alex (95715) 3 место. Jack (95715) Вот текст программы. type tgamer=record nik:string; bal:integer; end; var b,c:tgamer; a : array [1..4] of tgamer; i,n,k,m :integer; d,f:string; function FindNik(nik:string): integer; var i: integer; begin result :=-1; for i:=1 to 4 do if a [ i ].nik=nik then begin result :=i; exit end; end; function FindBal(bal:integer): integer; var i: integer; begin result:= -1; for i:=1 to 4 do if a[ i ].bal=bal then begin result:=i; exit end; end; procedure Sort; var i,j,k,m, max :integer; temp : tgamer; begin for i:=1 to 3 do begin max:=a [ i ] .bal; k:=i; for j:=i to 4 do if a[j].bal >max then begin max:=a[j].bal; k:=j; end; temp:=a[ i ]; a[ i ]:=a[k]; a[k]:=temp; end; end; begin readln (n); for i:=1 to n do begin read (k); readln(d); d:=Trim(d); f:=''; // обработать очередной результат m:= FindNik(d); if m>0 then begin if k>a[m].bal then a[m].bal:=k; end else begin a[4].bal:=k; a[4].nik:=d end; m:=FindBal(k); if m>0 then begin a[m].bal:= a[m].bal+1; f:=a[m].nik end; Sort; if f<>'' then begin m:=FindNik(f); a[m].bal:=a[m].bal-1; end; end; writeln ('1 место: ',a[1].nik, '(',a[1].bal,')'); writeln ('2 место: ',a[2].nik, '(',a[2].bal,')'); writeln ('3 место: ',a[3].nik, '(',a[3].bal,')'); end. Поясню некоторые моменты. Очередной кандидат в призеры помещается в массив на 4-е место. После этого массив сортируется по баллам и он может перейти на призовое место, если его результат окажется лучше другого. Сортировка не займет существенного времени, так как массив всего из 4-х элементов. Чтобы соблюсти условие, что участник с тем же количеством баллов, пришедший раньше должен занять лучшее место, мы ищем призера с тем же количеством баллов, m:=FindBal(k); if m>0 then begin a[m].bal:= a[m].bal+1; f:=a[m].nik end; и увеличиваем ему результат на 1, чтобы при сортировке он гарантированно встал на лучшее место. После сортировки мы у него эту 1 забираем. if f<>'' then begin m:=FindNik(f); a[m].bal:=a[m].bal-1; end; end; Что скажете?

MEA: и увеличиваем ему результат на 1, чтобы при сортировке он гарантированно встал на лучшее место. После сортировки мы у него эту 1 забираем. А если первые три участника имели равное количество баллов. 1 добавится только к первому из равных. Прием +1, -1 может привести к ошибке.

SergJP: Проверил, работает. Ввел всем одинаковые баллы, расположились в хронологическом порядке. 1 место: Jack(69485) 2 место: Nik(69485) 3 место: OK(69485) Вводил: Jack, Nik, OK, GK, IK


Поляков: SergJP пишет: Проверил, работает. Ввел всем одинаковые баллы, расположились в хронологическом порядке. Это не аргумент. Вы же знаете, что неполное тестирование программы не может доказать ее правильность, может только обнаружить ошибку (это Э. Дейкстра). Нужно доказать, что будет всегда работать. Я с ходу этого явно не вижу.

MEA: a : array [1..4] of tgamer; function FindNik(nik:string): integer; var i: integer; begin result :=-1; for i:=1 to 4 do if a.nik=nik then begin result :=i; exit end; end; Ваша версия программы отличается от приведенной здесь. Эта не компилируется.

SergJP: Прошу прощения, движок форума воспринимает [ i ] как символ форматирования шрифта. Замените a.nik на a [ i ].nik. сам только что заметил. Вроде все поправил.

MEA: Тест: 6 40 a 39 b 39 c 38 e 40 f 41 k 1 место: k(41) 2 место: f(40) 3 место: a(40) Участник f обошел участника a

SergJP: 6 40 a 39 b 39 c 38 e 40 f 41 k 1 место: k(41) 2 место: a(40) 3 место: f(40) MEA, благодарю за замечание. Немного доработал сортировку и запоминаю номер записи. При сортировке в случае равных значений максимальным считается тот, у кого меньший номер. Текст программы: //Вот текст программы. type tgamer=record nik:string; bal:integer; cnt : integer; end; var b,c:tgamer; a : array [1..4] of tgamer; i,n,k,m :integer; d,f:string; function FindNik(nik:string): integer; var i: integer; begin result :=-1; for i:=1 to 4 do if a [ i ].nik=nik then begin result :=i; exit end; end; function FindBal(bal:integer): integer; var i: integer; begin result:= -1; for i:=1 to 4 do if a[ i ].bal=bal then begin result:=i; exit end; end; procedure Sort; var i,j,k,m, max :integer; temp : tgamer; begin for i:=1 to 3 do begin max:=a [ i ] .bal; k:=i; for j:=i to 4 do if a[j].bal >max then begin max:=a[j].bal; k:=j; end else if a[j].bal = max then begin if a[j].cnt < a[k].cnt then begin max:=a[j].bal; k:=j; end; end; temp:=a[ i ]; a[ i ]:=a[k]; a[k]:=temp; end; end; begin readln (n); for i:=1 to n do begin read (k); readln(d); d:=Trim(d); f:=''; // обработать очередной результат m:= FindNik(d); if m>0 then begin if k>a[m].bal then a[m].bal:=k; end else begin a[4].bal:=k; a[4].nik:=d; a[4].cnt:=i; end; m:=FindBal(k); if m>0 then begin a[m].bal:= a[m].bal+1; f:=a[m].nik end; Sort; if f<>'' then begin m:=FindNik(f); a[m].bal:=a[m].bal-1; end; end; writeln ('1 место: ',a[1].nik, '(',a[1].bal,')'); writeln ('2 место: ',a[2].nik, '(',a[2].bal,')'); writeln ('3 место: ',a[3].nik, '(',a[3].bal,')'); end. //

MEA: Но мне кажется, что идея с "+1 " потом "-1" это не лучший вариант. Доверия не вызывает. И полагаю, что надо продолжить анализ и тестирование.

tavabar: Здравствуйте! Есть задача: Для заданной последовательности целых чисел необходимо найти максимальную сумму квадратов двух её элементов, номера которых различаются не менее чем на 10. Значение каждого элемента последовательности не превышает 100. Количество элементов последовательности не превышает 10000. И есть решение, которое эффективно по времени, но не эффективно по использованию памяти (3 балла): const d = 10; var N: integer; a: array[1..10000] of integer; {хранение всех элементов последовательности} mn:integer; {максимальное введенное число, не считаяd последних} m:integer; {максимальное значение суммы квадратов} i: integer; begin readln(N);{Ввод всех элементов последовательности} for i:=1 to N do readln(a); mn := 0; m := 0; for i := d + 1 to N do begin if a[i-d] > mn then mn := a[i-d]; if a*a+mn*mn > m then m := a*a+mn*mn end; writeln(m) end. Вопросы: 1) Почему это решение признается правильным, если оно достигает нужных целей не для любых входных данных: например, если последовательность состоит только из отрицательных целых чисел, то переменная mn не переопределяется и дает неверный вклад в конечную сумму. 2) Почему не учитывается, что квадрат отрицательного может быть больше квадрата положительного? 3)Почему переменная m имеет тип integer, а не longint, учитывая резкое увеличение чисел при возведении в степень? По пунктам 1-2 (для Borland Pascal 7.0). Предлагаю заменить строку программы: mn := 0; на mn:=-maxint; ИЛИ, учитывая особенность результата, строку if a[i-d] > mn then mn := a[i-d]; на if abs(a[i-d])> mn then mn := a[i-d]; Ваше мнение?

Поляков: tavabar пишет: если последовательность состоит только из отрицательных целых чисел Нужно внимательно посмотреть условие оригинала. Наверное, указано, что там положительные числа. Если есть отрицательные, то, конечно, неверно. не учитывается, что квадрат отрицательного может быть больше квадрата положительного? См. выше. mn:=-maxint; Это нехорошо. Лучше mn:=a[1]; if abs(a[i-d])> mn then mn := a[i-d]; Это вполне разумно.

tavabar: Поляков пишет: Нужно внимательно посмотреть условие оригинала. Наверное, указано, что там положительные числа. Условие скопировано.

OlgaChe: 42) На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Чтобы в документации качественно отличать одну серию от другой, каждую серию решили характеризовать числом, равным минимальному произведению из всех произведений пар скоростей различных частиц. Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя искомую величину. В нашей модели скорость частицы - это величина, которая может принимать как положительные, так и отрицательные значения. Следует учитывать, что частиц, скорость которых измерена, может быть очень много, но не может быть меньше двух. Перед текстом задачи кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строке подается количество частиц N. В каждой из последующих N строк записано одно целое число со знаком (плюс или минус), по абсолютной величине не превосходящее 10000. Пример входных данных: 5 +123 +2000 +10 +3716 +10 Программа должна вывести одно число - минимальное произведение из всех произведений пар скоростей различных частиц. Пример выходных данных для приведенного выше примера входных данных: 100 [pre2]var n, max, min, pmin1, pmin2, nmax1, nmax2, m, i : integer; f1, f2 : boolean; begin f1 := false; f2 := false; max := -100001; min := 100001; nmax1 := -100001; nmax2 := -100001; pmin1 := 100001; pmin2 := 100001; readln(n); for i := 1 to n do begin readln(m); if (m >= 0) then f1 := true; if (m < 0) then f2 := true; if (m > max) then max := m; if (m < min) then min := m; if (m >= 0) and (m <= pmin1) then begin pmin2 := pmin1; pmin1 := m; end; if (m >= 0) and (m > pmin1) and (m <= pmin2) then pmin2 := m; if (m < 0) and (m >= nmax1) then begin nmax2 := nmax1; nmax1 := m; end; if (m < 0) and (m < nmax1) and (m >= nmax2) then nmax2 := m; end; if (f1 = f2) then writeln(max*min) else if (f1 = true) then writeln(pmin1*pmin2) else if (f2 = true) then writeln(nmax1*nmax2); end. [/pre2]

Поляков: OlgaChe пишет: Оцените, пожалуйста, решение задачи №42 В целом решение правильное и эффективное, на полный балл. Только вместо [pre2] if (f1 = true) then ...[/pre2] лучше писать [pre2] if f1 then ...[/pre2] А ещё лучше называть флаги как-то более информативно, чем f1 и f2. Хотя это не ошибка, за это баллы на ЕГЭ не снижают.



полная версия страницы