Отправлено: 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. 
 

 Отправлено: 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 эти средства тоже есть. Нужно переходить с устаревших языков на современный уровень.