Задание С-4. Где ошибка?
Здравствуйте! Я получил за задание С-4 0 баллов. Не очень приятно, учитывая что все остальные задания сделал абсолютно верно. Не могли бы вы помочь совершить работу над ошибками? Где я налажал?
По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности - наибольшее число R, удовлетворяющее следующим условиям:
1)R - произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2)R делится на 33.
Если такого числа R нет, то контрольное значение полагается равным 0.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: ...
Контроль пройден (или- Контроль не пройден)
Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Пример входных данных:
6
550
33
7
997
9
60
33000
Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 33000 Контроль пройден
С4
Собственно мой код:
По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности - наибольшее число R, удовлетворяющее следующим условиям:
1)R - произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2)R делится на 33.
Если такого числа R нет, то контрольное значение полагается равным 0.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: ...
Контроль пройден (или- Контроль не пройден)
Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Пример входных данных:
6
550
33
7
997
9
60
33000
Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 33000 Контроль пройден
С4
Собственно мой код:
Код:
var
N: longint;
a: array [1..N] of integer;
check, indek, y, i: integer;
z: boolean;
begin
z:=false;
readln (N);
for i:=1 to N do
readln (a[i]);
readln (check);
for i:=1 to N do begin
y:=a[i];
indeks:=i;
for i:=1 to N do begin
if (check=y*a[i]) and (indeks<>i) then z:=true;
end;
*тут я забыл один end, похоже*
writeln ('Вычислительное контрольное значение:', x) //тут я взял переменную из черновика, my bad. Должно быть check
if (z=true) and (check mod 33 = 0) then
writeln ('Контроль пройден')
else
writeln ('Контроль не пройден');
end.
N: longint;
a: array [1..N] of integer;
check, indek, y, i: integer;
z: boolean;
begin
z:=false;
readln (N);
for i:=1 to N do
readln (a[i]);
readln (check);
for i:=1 to N do begin
y:=a[i];
indeks:=i;
for i:=1 to N do begin
if (check=y*a[i]) and (indeks<>i) then z:=true;
end;
*тут я забыл один end, похоже*
writeln ('Вычислительное контрольное значение:', x) //тут я взял переменную из черновика, my bad. Должно быть check
if (z=true) and (check mod 33 = 0) then
writeln ('Контроль пройден')
else
writeln ('Контроль не пройден');
end.
Не знаю какой у вас паскаль, но в борландском не задаются так массивы:
Я бы сделал так:
И потом в коде:
Так что не стоит переживать что вы end забыли, код не рабочий начиная с объявления переменных.
В сам алгоритм не вдумывался, нет времени, тут над своими алгоритмами в матлабе работы по горло.
Код:
var
a: array [1..N] of integer;
a: array [1..N] of integer;
Код:
var
a: Array of WORD;
a: Array of WORD;
Код:
z := false;
readln(N);
SetLength(a, N); // Вот теперь будет массив [0..N - 1]
readln(N);
SetLength(a, N); // Вот теперь будет массив [0..N - 1]
Так что не стоит переживать что вы end забыли, код не рабочий начиная с объявления переменных.
В сам алгоритм не вдумывался, нет времени, тут над своими алгоритмами в матлабе работы по горло.
Низкий бал говорите получили? Меня это не удивляет.
Почему не используете 1-ый элемент массива? Не ошибка конечно, но если решение пограничное об оценке то скорее всего перевес будет не в вашу пользу.
Почему не используете 1-ый элемент массива? Не ошибка конечно, но если решение пограничное об оценке то скорее всего перевес будет не в вашу пользу.
Да........... В целом багокод.
Второй и третий for в вашем коде, вы же пишите:
Почему у вас счётчики цикла и вложенного в него цикла совпадают?
Не загружал код в студию, но думаю она будет останавливаться на 30% строк этого кода )))
А если ещё есть ошибки в алгоритме то кол с минусом обеспечен )))
Второй и третий for в вашем коде, вы же пишите:
Код:
for i:=1 to N do begin // Что означает выполнять в цикле не одну строчку, а всё до end
y:=a[i];
indeks:=i;
for i:=1 to N do begin
if (check=y*a[i]) and (indeks<>i) then z:=true;
end;
y:=a[i];
indeks:=i;
for i:=1 to N do begin
if (check=y*a[i]) and (indeks<>i) then z:=true;
end;
Не загружал код в студию, но думаю она будет останавливаться на 30% строк этого кода )))
А если ещё есть ошибки в алгоритме то кол с минусом обеспечен )))
Как писалось выше, в Вашей программе довольно много "опечаток", из-за которых программа просто не запустится! Не говоря уже про то, что сам алгоритм по меньшей мере неэффективный.
В любом случае не запускается программа - не выдает ответ - 0 баллов.
1) как писал QWERYTY, нельзя писать
можно было написать следующим образом:
но таким способом вы уже заведомо обрекаете на неудачу при N>MaxN! При этом, если цепочка чисел будет например = 100, то ещё 32*(30000-100)бит памяти будут потрачены впустую.
Поэтому лучше описывать динамический массив (начинается с 0)
2) в описании переменных (Var) объявлена переменная indek, но в программе 2 раза используется переменная indeks
3) В выражении writeln('Вычислительное контрольное значение:', x) используется "какой-то х" из вашего "какого-то" черновика ("мое плохое"). При этом после скобки должна быть точка с запятой.
4) для проверки условия Вы используете 2 цикла (for) - один вложен во второй - и при этом переменная цикла одна и та же (i), хотя требовалось взять ещё одну переменную (например j).
И соответственно не будут использоваться переменные y и indeks: необходимо будет писать
При этом лучше сперва сравнивать индексы, а только потом произведение чисел!
Если это ВСЁ исправить, тогда программа будет работать и даже выдавать правильный ответ.
НО даже после всего этого я бы больше 5 баллов из 10 не поставил по следующим причинам.
В задании написано "... Количество чисел известно, но может быть очень велико ...". Я конечно очень недоволен такой неадекватной формулировкой, т.к. понятие "очень велико" в этой задаче мне не понятно до конца. Для экзаменаторов и школьников\студентов это может означать 200-900. Для меня же сочетание "очень велико" подразумевает 1000 000 - 100 000 000 и выше.
Также в задании написано "Напишите эффективную, в том числе по используемой памяти, программу"
При N>1000
1) размер массива растет пропорционально N, т.е. при N=1000000 длина массива будет равна 1000000. Что для такой простенькой программы многовато.
Хотите спросить, что же тут можно изменить. Ну если Вам влом думать, отвечу. Взять массив с индексами от 1 до 1000. Почему и как - домашнее задание ;)
2) поиск ответа при вашем алгоритме возрастает квадратично N.При N=10000 - программа будет думать меньше секунды, при N=50000 - 4 секунды, при N=100000 - 19сек при N=300000 - 2мин59сек, 500000 - 8:22, при 1000000 - не дождался ....
Это реальные данные, проверенные на Intel Core 2 Duo E4700 (2.6GHz) ;)
Если использовать Вашу программу с динамическим массивам (а не как я предложил с массивом из тысячи элементов), то в вашем алгоритме можно поправить минимум 3 вещи:
1) Если R (в вашей программе переменная check) не делиться на 33, то ЗАЧЕМ, я спрашиваю "Зачем", вычислять ещё что-то!!!
2) Второй цикл for j := 0 to N - 1 do (это уже когда я исправил ваши "опечатки" - см выше) надо начинать не с 0, а с i+1. Заодно отпадает сразу и проверка i<>j.
3) Если вы обнаружили , что произведение , например, первого и второго чисел дают вам контрольное число R, то спрашивается зачем выполнять ещё миллионы и миллиарды вычислений??? Или мы не знаем, что кроме цикла for есть while? да хотя бы break использовать.
А если вы возьмете статический массив от 1 до 1000, как я писал выше, то вам понадобиться для решения программы вам максимум понадобиться 1000000 операций, что займет <1с при любых N.
Исходя из всего выше написанного, я очень сомневаюсь, что "... все остальные задания сделал абсолютно верно ..."
В любом случае не запускается программа - не выдает ответ - 0 баллов.
1) как писал QWERYTY, нельзя писать
Код:
var
N: longint;
a: array [1..N] of integer;
N: longint;
a: array [1..N] of integer;
можно было написать следующим образом:
Код:
const
MaxN = 30000;
var
a: array [1 .. MaxN] of integer;
MaxN = 30000;
var
a: array [1 .. MaxN] of integer;
Поэтому лучше описывать динамический массив (начинается с 0)
Код:
var
N: longint;
a: array of integer;
...
begin
readln(N);
SetLength(a, N);
N: longint;
a: array of integer;
...
begin
readln(N);
SetLength(a, N);
2) в описании переменных (Var) объявлена переменная indek, но в программе 2 раза используется переменная indeks
3) В выражении writeln('Вычислительное контрольное значение:', x) используется "какой-то х" из вашего "какого-то" черновика ("мое плохое"). При этом после скобки должна быть точка с запятой.
4) для проверки условия Вы используете 2 цикла (for) - один вложен во второй - и при этом переменная цикла одна и та же (i), хотя требовалось взять ещё одну переменную (например j).
И соответственно не будут использоваться переменные y и indeks: необходимо будет писать
Код:
if (check = a[i] * a[j]) and (i <> j) then
Если это ВСЁ исправить, тогда программа будет работать и даже выдавать правильный ответ.
НО даже после всего этого я бы больше 5 баллов из 10 не поставил по следующим причинам.
В задании написано "... Количество чисел известно, но может быть очень велико ...". Я конечно очень недоволен такой неадекватной формулировкой, т.к. понятие "очень велико" в этой задаче мне не понятно до конца. Для экзаменаторов и школьников\студентов это может означать 200-900. Для меня же сочетание "очень велико" подразумевает 1000 000 - 100 000 000 и выше.
Также в задании написано "Напишите эффективную, в том числе по используемой памяти, программу"
При N>1000
1) размер массива растет пропорционально N, т.е. при N=1000000 длина массива будет равна 1000000. Что для такой простенькой программы многовато.
Хотите спросить, что же тут можно изменить. Ну если Вам влом думать, отвечу. Взять массив с индексами от 1 до 1000. Почему и как - домашнее задание ;)
2) поиск ответа при вашем алгоритме возрастает квадратично N.При N=10000 - программа будет думать меньше секунды, при N=50000 - 4 секунды, при N=100000 - 19сек при N=300000 - 2мин59сек, 500000 - 8:22, при 1000000 - не дождался ....
Это реальные данные, проверенные на Intel Core 2 Duo E4700 (2.6GHz) ;)
Если использовать Вашу программу с динамическим массивам (а не как я предложил с массивом из тысячи элементов), то в вашем алгоритме можно поправить минимум 3 вещи:
1) Если R (в вашей программе переменная check) не делиться на 33, то ЗАЧЕМ, я спрашиваю "Зачем", вычислять ещё что-то!!!
2) Второй цикл for j := 0 to N - 1 do (это уже когда я исправил ваши "опечатки" - см выше) надо начинать не с 0, а с i+1. Заодно отпадает сразу и проверка i<>j.
3) Если вы обнаружили , что произведение , например, первого и второго чисел дают вам контрольное число R, то спрашивается зачем выполнять ещё миллионы и миллиарды вычислений??? Или мы не знаем, что кроме цикла for есть while? да хотя бы break использовать.
А если вы возьмете статический массив от 1 до 1000, как я писал выше, то вам понадобиться для решения программы вам максимум понадобиться 1000000 операций, что займет <1с при любых N.
Исходя из всего выше написанного, я очень сомневаюсь, что "... все остальные задания сделал абсолютно верно ..."