Автор | Сообщение |
|
Отправлено: 06.05.17 11:16. Заголовок: 27-70 (Д. Муфаззалов, Уфа)
Здравствуйте. Есть вопросы по условию задачи и по ее решению. Условие: На вход программы поступает последовательность из N натуральных чисел, каждое из которых не больше 1000. Требуется вывести цифры, встречающиеся в эти числах, в порядке неубывания частоты их появления. Если какие-то цифры встречаются одинаковое число раз, они выводятся в порядке убывания. Входные данные: На вход программе подаётся натуральное число N (N <= 1000), а затем N натуральных чисел, каждое из которых не превышает 10000. В решении этой задачи определяется "общее количество цифр во вводимых числах," а после выполняется цикл столько раз, сколько нашлось всего цифр. Но разве их не может быть очень много? Значит и цикл будет выполняться очень много раз? Я составила свой вариант решения этой задачи. И хотелось бы узнать, могут ли за нее поставить 4 балла. var a: array[0..9] of word; j, n, i, num, s, min, h: integer; begin readln(n); for i:=0 to 9 do a[i ]:=0; for i := 1 to n do begin readln(num); while num > 0 do begin s:= num mod 10; a[s ] := a[s ] + 1; num := num div 10; end end; for i := 0 to 9 do if a[i ] <> 0 then begin s:= i; break; end; for i := s to 9 do begin min:= s; while (a[min] = 0) and (min < 9) do min:= min + 1; if a[min] = 0 then break; for j:= min to 9 do if (a[j]<>0) and (a[j] < a[min]) then min:=j; for h:= 9 downto s do if (a[min] = a[h]) and (a[h] <> 0) then begin write(h, ' '); a[h]:= 0; end; end; end.
| |
|
Ответов - 23
, стр:
1
2
All
[только новые]
|
|
|
Отправлено: 06.05.17 11:49. Заголовок: В предыдущем сообщен..
| |
|
|
| Администратор
|
Сообщение: 1415
|
|
Отправлено: 06.05.17 15:40. Заголовок: DragonflyLif пишет: ..
DragonflyLif пишет: цитата: | Я составила свой вариант решения этой задачи |
|
Мне не ясно, чем он лучше приведенного в разборе.
| |
|
|
Отправлено: 06.05.17 15:54. Заголовок: Я не утверждаю, что ..
Я не утверждаю, что он лучше. Программа, очевидно, более громоздкая. Больше циклов (но в них ограниченное количество действий). Я хотела, чтобы количество действий в цикле не зависело от общего количества цифр в числах. Ведь получается, если чисел очень много, то программа будет выполняться дольше. И еще есть вопрос. Решение этой задачи, представленное на сайте является эффективным по времени? Если да, то конечно его использовать удобнее.
| |
|
|
| Администратор
|
Сообщение: 1417
|
|
Отправлено: 07.05.17 12:42. Заголовок: DragonflyLif пишет: ..
DragonflyLif пишет: цитата: | Я хотела, чтобы количество действий в цикле не зависело от общего количества цифр в числах. |
|
В вашем решение все равно такая зависимость есть - см. цикл for, где вводятся данные. Думаю, что вы что-то путаете. цитата: | Решение этой задачи, представленное на сайте является эффективным по времени? |
|
Да.
| |
|
|
Отправлено: 11.05.17 22:17. Заголовок: DragonflyLif пишет: ..
DragonflyLif пишет: цитата: | В решении этой задачи определяется "общее количество цифр во вводимых числах," а после выполняется цикл столько раз, сколько нашлось всего цифр. Но разве их не может быть очень много? Значит и цикл будет выполняться очень много раз? |
| Более того, ваша программа становится менее эффективна по памяти, т.к. используете больше переменных, чем Д. Муфаззалов, а сложность алгоритма приблизительно одна и та же.
| |
|
|
Отправлено: 12.05.17 00:15. Заголовок: Добрый вечер! Извин..
Добрый вечер! Извиняюсь, что вклиниваюсь в беседу. Ради интереса глянул варианты решения программы, сразу зародился свой. В начале предлагаю в одном цикле считывать не числа, а символы. Пробелы и\или переводы строк при этом игнорировать. Тогда не придется каждый раз крутить цикл с выделением цифр из числа. Но это не главная идея. Особенно мне не понравилась идея с этой переменной count. Цифр же действительно может быть очень много. В худшем случае 40 тыс. (в варианте, как писали выше, опечатка)! Предлагаю свой вариант этого фрагмента. В худшем случае (все элементы разные и отличны от нуля) массив придется просматривать 10 раз (то есть 10 раз по 10 элементов), присваиваний тоже не более нескольких десятков (учитывая присваивания перед циклом for). int max2, max1 = -1; do { max2 = max1; max1 = 0; for (int j=0; j<10; j++) { if (a[j] > max1) max1 = a[j]; if (a[j] == max2) { cout << j << " "; a[j] = 0; } } } while (max1>0);
| |
|
|
Отправлено: 12.05.17 08:30. Заголовок: Dm пишет: В начале ..
Dm пишет: цитата: | В начале предлагаю в одном цикле считывать не числа, а символы. Пробелы и\или переводы строк при этом игнорировать. Тогда не придется каждый раз крутить цикл с выделением цифр из числа. Но это не главная идея. |
| А можете по подробнее про символы? Ведь всё равно придётся обрабатывать строку для вычленения этих символов из ввода пользователя, или я ошибаюсь?
| |
|
|
Отправлено: 12.05.17 13:03. Заголовок: Sidr, если в паскале..
Sidr, если в паскале, то можно так: var s: string[4]; ... begin readln(n); {Инициализация массива счетчиков} .... for j:=1 to n do begin Readln(s); for k:= 1 to length(s) do inc(a[ord(s[k])-ord('0')]); end; ... Такой подход позволяет избежать делений. На С++ можно попробовать сделать всё в одном цикле, считывать символы функцией getch(). Количество прочитанных чисел можно определять, отлавливая '\n'.
| |
|
|
Отправлено: 12.05.17 13:42. Заголовок: Эхх, на Паскале... Я..
Эхх, на Паскале... Я-то на Си пишу все задачки, поэтому мне эффективная по времени и памяти обработка строк очень трудно даётся. Ничего путного в голову не лезет...Функция atoi выведет сразу всё число в строке,чтобы она этого не делала придётся что-то придумывать мудрённое. Если рассматривать каждую строку, то для обработки опять же нужен будет либо цикл for либо while, дабы вычленять символы цифр из каждого числа.
| |
|
|
Отправлено: 12.05.17 14:07. Заголовок: Sidr, так надо забыт..
Sidr, так надо забыть Си и его функции как страшный сон. Для чего придумали C++ и класс string? ;-) #include <string> #include <iostream> using namespace std; int main() { string s; cin >> s; // Ввели строку for (int j=0; j<s.size(); j++) cout << s[j]; // Вывели посимвольно return 0; } Можно проверить на http://cpp.sh. Одни удобства на мой взгляд.
| |
|
|
| Администратор
|
Сообщение: 1439
|
|
Отправлено: 13.05.17 12:22. Заголовок: Dm пишет: Такой подх..
Dm пишет: цитата: | Такой подход позволяет избежать делений. |
|
Не факт, что это более эффективно. Можете доказать?
| |
|
|
|
Отправлено: 13.05.17 13:00. Заголовок: Поляков, если в худш..
Поляков, если в худшем случае: 10 тыс. чисел, каждое равно 1000. Суммарно циклы while произведут 40 тыс. операций div и столько же mod, причём на 10 (деление и остатки на 2 можно было бы заменить сдвигами). И для каждого из чисел по 4 сравнения в условии цикла. При считывании строк также 4 сравнения в цикле for, зато 0 делений, вместо них будут лишь вычитания. Операций mod тоже 0. Можно, конечно, предположить, что массив потребует 4 операций ввода вместо одной, но это уже больше от компилятора зависит. Вводимые данные всё равно прежде буферизируются, а память считывается с опережением, так что всё также будет в кэше. Попробую определить время ввода из файла сегодня вечером и сообщу результат эксперимента.
| |
|
|
Отправлено: 13.05.17 21:53. Заголовок: Как и обещал, написа..
Как и обещал, написал программу для сравнения двух вариантов ввода чисел и выделения из них всех цифр. Вариант А - считываем данные как числа, с помощью целочисленных делений и взятия остатков выделяем из них цифры. Вариант Б - считываем данные как строки, далее трактуем их как массивы цифр. Программа на PascalABC получилась такая: Скрытый текст
const N = 100000; var a: array[0..9] of integer; f: textfile; i, x, k: integer; s: string[5]; begin assign(f, 'test.txt'); rewrite(f); for i:= 1 to N do writeln(f, random(30000)); close(f); {Вариант А} for k:= 0 to 9 do a[k]:= 0; reset(f); var d := Milliseconds; for i:= 1 to N do begin readln(f, x); while x > 0 do begin inc(a[x mod 10]); x:= x div 10 end; end; close(f); writeln((Milliseconds-d)/1000); {Вариант Б} for k:= 0 to 9 do a[k]:= 0; reset(f); d := Milliseconds; k:= ord('0'); for i:= 1 to N do begin readln(f, s); for x:= 1 to length(s) do inc(a[ord(s[x])-k]); end; close(f); writeln((Milliseconds-d)/1000); end.
| Первоначально в варианте Б я поленился вычислить заранее код символа '0', поэтому время работы получалось немного больше. В нынешнем виде результаты тестов такие (я не стал осреднять, разница от теста к тесту ничтожно мала): вариант А: 0.039 вариант Б: 0.046 Но простая замена string[5] на string сразу всё меняет: вариант А: 0.039 вариант Б: 0.015 Так что, как я и предполагал, многое зависит от компилятора и "мелочей" в коде. Хотя и нет многократного выигрыша в эффективности, вариант Б более универсален. Если на входе будут большие числа, алгоритм со строками даже не придется особо менять.
| |
|
|
| Администратор
|
Сообщение: 1441
|
|
Отправлено: 13.05.17 22:02. Заголовок: Dm пишет: Хотя и нет..
Dm пишет: цитата: | Хотя и нет многократного выигрыша в эффективности, вариант Б более универсален. |
|
С одной стороны. А с другой стороны, если данные уже заранее загружены в массив, другого варианта, как делением, нет. Или есть?
| |
|
|
Отправлено: 13.05.17 22:08. Заголовок: Если уже есть массив..
Если уже есть массив из чисел, разумеется, нет никакого смысла в его преобразовании в массив строк. Но если есть массив строк, то тоже сомневаюсь в целесообразности преобразовывать строки в числа. Нужно сразу считывать данные в удобном для дальнейшей обработки формате.
| |
|
|
Отправлено: 12.05.17 15:55. Заголовок: Dm пишет: int max2,..
Dm пишет: цитата: | int max2, max1 = -1; do { max2 = max1; max1 = 0; for (int j=0; j<10; j++) { if (a[j] > max1) max1 = a[j]; if (a[j] == max2) { cout << j << " "; a[j] = 0; } } } while (max1>0); |
| Вот эта штука не хочет сортировать элементы массива в порядке неубывания. Проверял в GCC на Си. На IDEONE(C++) тоже не работает,потому что на самом деле выводит числа в порядке убывания, вместо НЕУБЫВАНИЯ. Вот ввод: int a[10]={5,2,3,10,20,4,1,320,80,100}; А вот вывод:7 9 8 4 3 0 5 2 1 6 ИЛИ 320 100 80 20 10 5 4 3 2 1 если выводить частоту цифр.
| |
|
|
Отправлено: 12.05.17 17:22. Заголовок: Sidr, действительно ..
Sidr, действительно перепутал условие задачи. Тогда меняем всюду max на min и немного дополняем if: if (a[j] > 0 && (a[j] < min1 || min1<=0)) min1 = a[j]; Вчера ночью писал, сейчас в метро еду. Так что поправьте сами, если что не так. Надеюсь, что сама идея ясна. :-)
| |
|
|
Отправлено: 12.05.17 21:15. Заголовок: Dm пишет: if (a ..
Dm пишет: цитата: | if (a[j] > 0 && (a[j] < min1 || min1<=0)) min1 = a[j]; |
| Ваш код всё равно не выводит нужную последовательность, ведь при одинаковых значениях частот a их нужно выводить в порядке убывания, он же выводит их подряд + если j=0 и a[j]=0 код так же не выполняется. Я это пишу не с целью съязвить или унизить, а на всякий случай,вдруг Вам это нужно. А вообще, спасибо Вам большое за то, что побудили узнать "а чо будет происходить если запихнуть цикл for в while". Теперь я знаю :)
| |
|
|
Отправлено: 12.05.17 22:19. Заголовок: Sidr, мне не сложно ..
Sidr, мне не сложно что-то подсказать, просто часто нет возможности что-то скомпилировать и проверить. Сейчас дома, поэтому перечитал условие и написал полностью код. Тоже была мелочь - просто с конца этот массив теперь обрабатываем. int min2, min1 = -1; do { min2 = min1; min1 = 0; for (int j=9; j>=0; j--) { if (a[j] > 0 && (a[j] < min1 || min1<=0)) min1 = a[j]; if (a[j] == min2) { cout << j << " "; a[j] = 0; } } } while (min1>0); И ссылка, чтобы потестировать: http://ideone.com/sFV9DD Если ЕГЭ в этом году, то срочно нужно самостоятельно экспериментировать с кодом, ведь поправить пару ошибок вроде моих - это же 24 задача в чистом виде. :-)
| |
|
|
Отправлено: 13.05.17 02:30. Заголовок: Dm пишет: Sidr, мне..
Dm пишет: цитата: | Sidr, мне не сложно что-то подсказать, просто часто нет возможности что-то скомпилировать и проверить. Сейчас дома, поэтому перечитал условие и написал полностью код. Тоже была мелочь - просто с конца этот массив теперь обрабатываем. int min2, min1 = -1; do { min2 = min1; min1 = 0; for (int j=9; j>=0; j--) { if (a[j] > 0 && (a[j] < min1 || min1<=0)) min1 = a[j]; if (a[j] == min2) { cout << j << " "; a[j] = 0; } } } while (min1>0); И ссылка, чтобы потестировать: http://ideone.com/sFV9DD Если ЕГЭ в этом году, то срочно нужно самостоятельно экспериментировать с кодом, ведь поправить пару ошибок вроде моих - это же 24 задача в чистом виде. :-) |
| Спасибо Вам огромное. К слову, я действительно разобрался в чём суть вашего алгоритма и сделал так, чтобы он выводил и те цифры, которые не встречаются в последовательности вообще. ( т.е. на выход выдавались и те индексы, значения элементов которых равны нулю ) http://ideone.com/yAJywy
| |
|
|
Отправлено: 13.05.17 08:48. Заголовок: Sidr, пожалуйста. Ра..
Sidr, пожалуйста. Рад, что получилось в нём разобраться. ))
| |
|
|
|
Отправлено: 12.05.17 08:36. Заголовок: DM если Вам не трудн..
DM если Вам не трудно и будет удобно, то можно выкладывать в своих комментариях код либо на Паскале, либо на Питоне. В большинстве школ Российской глубинке основным языком для изучения программирования является Паскаль, а не С++. Это будет в одной линии с К.Ю.Поляковым, который в разборах задач 25 и 27 выкладывает разбор на Паскале.
| |
|
|
Отправлено: 12.05.17 11:23. Заголовок: nikson, питон как ра..
nikson, питон как раз сложнее для понимания знатокам Паскаля. Но хорошо, буду писать на Паскале, хотя я и не использовал никакие специфические команды С++. Но всё-таки лучше решать такие задачи на С++, активно пользуясь более современными приёмами. Поясню сказанное в общих чертах на примере этой же задачи. В программе на С++ можно создать либо словарь map, либо вектор vector из структур такого вида: struct dic { char key; // ключ, то есть символы '0'..'9' int val; // счётчик }; Если работать с вектором структур, то нужно заполнить индексы key и счётчики val, считывая числа как строки string. Но потом одной командой sort можно отсортировать этот вектор и вывести все key, начиная с первого ненулевого val. Сортировка будет гораздо эффективнее предложенного авторского метода с count. Ну что такое отсортировать массив из 10 элементов, тем более, не пузырьком, а приличным методом? :-) Если же работать со словарём, то заполнить его очень легко, но сортировать будет проблемно. Зато можно использовать аналог алгоритма, который я предлагал в первом сообщении. В итоге: раз в "глубинке" есть Интернет и компьютеры, то вполне реально эти приёмы изучить самостоятельно. Но, конечно, не за две недели до экзамена. В идеале с начала 10 класса, хотя за 11 класс это тоже реально. Как бонус будет возможность использовать подобные знания на олимпиадах, там они явно пригодятся. Кстати,в питоне и PascalABC эти средства тоже есть. Нужно переходить с устаревших языков на современный уровень.
| |
|
Ответов - 23
, стр:
1
2
All
[только новые]
|
|
|