На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение



Сообщение: 14
ссылка на сообщение  Отправлено: 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.


Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 23 , стр: 1 2 All [только новые]





Сообщение: 15
ссылка на сообщение  Отправлено: 06.05.17 11:49. Заголовок: В предыдущем сообщен..


В предыдущем сообщении программа была скопирована с ошибками.
Прикрепляю ссылку на файл с этой программой
http://file.qip.ru/office/RmATN5We/27_70.html


Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 1415
ссылка на сообщение  Отправлено: 06.05.17 15:40. Заголовок: DragonflyLif пишет: ..


DragonflyLif пишет:
 цитата:
Я составила свой вариант решения этой задачи

Мне не ясно, чем он лучше приведенного в разборе.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 16
ссылка на сообщение  Отправлено: 06.05.17 15:54. Заголовок: Я не утверждаю, что ..


Я не утверждаю, что он лучше. Программа, очевидно, более громоздкая. Больше циклов (но в них ограниченное количество действий). Я хотела, чтобы количество действий в цикле не зависело от общего количества цифр в числах. Ведь получается, если чисел очень много, то программа будет выполняться дольше.
И еще есть вопрос. Решение этой задачи, представленное на сайте является эффективным по времени?
Если да, то конечно его использовать удобнее.


Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 1417
ссылка на сообщение  Отправлено: 07.05.17 12:42. Заголовок: DragonflyLif пишет: ..


DragonflyLif пишет:
 цитата:
Я хотела, чтобы количество действий в цикле не зависело от общего количества цифр в числах.

В вашем решение все равно такая зависимость есть - см. цикл for, где вводятся данные. Думаю, что вы что-то путаете.
 цитата:
Решение этой задачи, представленное на сайте является эффективным по времени?

Да.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 7
ссылка на сообщение  Отправлено: 11.05.17 22:17. Заголовок: DragonflyLif пишет: ..


DragonflyLif пишет:

 цитата:
В решении этой задачи определяется "общее количество цифр во вводимых числах," а после выполняется цикл столько раз, сколько нашлось всего цифр. Но разве их не может быть очень много? Значит и цикл будет выполняться очень много раз?


Более того, ваша программа становится менее эффективна по памяти, т.к. используете больше переменных, чем Д. Муфаззалов, а сложность алгоритма приблизительно одна и та же.

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 16
ссылка на сообщение  Отправлено: 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);


Чтобы понять рекурсию, надо понять рекурсию Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 8
ссылка на сообщение  Отправлено: 12.05.17 08:30. Заголовок: Dm пишет: В начале ..


Dm пишет:

 цитата:
В начале предлагаю в одном цикле считывать не числа, а символы. Пробелы и\или переводы строк при этом игнорировать. Тогда не придется каждый раз крутить цикл с выделением цифр из числа. Но это не главная идея.


А можете по подробнее про символы? Ведь всё равно придётся обрабатывать строку для вычленения этих символов из ввода пользователя, или я ошибаюсь?

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 18
ссылка на сообщение  Отправлено: 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'.

Чтобы понять рекурсию, надо понять рекурсию Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 9
ссылка на сообщение  Отправлено: 12.05.17 13:42. Заголовок: Эхх, на Паскале... Я..


Эхх, на Паскале... Я-то на Си пишу все задачки, поэтому мне эффективная по времени и памяти обработка строк очень трудно даётся.
Ничего путного в голову не лезет...Функция atoi выведет сразу всё число в строке,чтобы она этого не делала придётся что-то придумывать мудрённое. Если рассматривать каждую строку, то для обработки опять же нужен будет либо цикл for либо while, дабы вычленять символы цифр из каждого числа.

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 19
ссылка на сообщение  Отправлено: 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. Одни удобства на мой взгляд.

Чтобы понять рекурсию, надо понять рекурсию Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 1439
ссылка на сообщение  Отправлено: 13.05.17 12:22. Заголовок: Dm пишет: Такой подх..


Dm пишет:
 цитата:
Такой подход позволяет избежать делений.

Не факт, что это более эффективно. Можете доказать?

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 23
ссылка на сообщение  Отправлено: 13.05.17 13:00. Заголовок: Поляков, если в худш..


Поляков, если в худшем случае: 10 тыс. чисел, каждое равно 1000. Суммарно циклы while произведут 40 тыс. операций div и столько же mod, причём на 10 (деление и остатки на 2 можно было бы заменить сдвигами). И для каждого из чисел по 4 сравнения в условии цикла.
При считывании строк также 4 сравнения в цикле for, зато 0 делений, вместо них будут лишь вычитания. Операций mod тоже 0.
Можно, конечно, предположить, что массив потребует 4 операций ввода вместо одной, но это уже больше от компилятора зависит. Вводимые данные всё равно прежде буферизируются, а память считывается с опережением, так что всё также будет в кэше.
Попробую определить время ввода из файла сегодня вечером и сообщу результат эксперимента.

Чтобы понять рекурсию, надо понять рекурсию Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 24
ссылка на сообщение  Отправлено: 13.05.17 21:53. Заголовок: Как и обещал, написа..


Как и обещал, написал программу для сравнения двух вариантов ввода чисел и выделения из них всех цифр.
Вариант А - считываем данные как числа, с помощью целочисленных делений и взятия остатков выделяем из них цифры.
Вариант Б - считываем данные как строки, далее трактуем их как массивы цифр.

Программа на PascalABC получилась такая:
Скрытый текст


Первоначально в варианте Б я поленился вычислить заранее код символа '0', поэтому время работы получалось немного больше. В нынешнем виде результаты тестов такие (я не стал осреднять, разница от теста к тесту ничтожно мала):
 
вариант А: 0.039
вариант Б: 0.046

Но простая замена string[5] на string сразу всё меняет:
 
вариант А: 0.039
вариант Б: 0.015


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

Чтобы понять рекурсию, надо понять рекурсию Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 1441
ссылка на сообщение  Отправлено: 13.05.17 22:02. Заголовок: Dm пишет: Хотя и нет..


Dm пишет:
 цитата:
Хотя и нет многократного выигрыша в эффективности, вариант Б более универсален.

С одной стороны. А с другой стороны, если данные уже заранее загружены в массив, другого варианта, как делением, нет. Или есть?

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 25
ссылка на сообщение  Отправлено: 13.05.17 22:08. Заголовок: Если уже есть массив..


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

Чтобы понять рекурсию, надо понять рекурсию Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 23 , стр: 1 2 All [только новые]
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

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