Отправляет email-рассылки с помощью сервиса Sendsay

Решение задач по программированию + разбор алгоритма

Подписаться Бесплатная новостная рассылка Подписчиков 9 RSS
  Октябрь 2006   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Открыта: 25-10-2006

Автор
Alle

Статистика

9 подписчиков
0 за неделю
←   Все выпуски   →

Решение задач по программированию + разбор алгоритма


Олимпиады.
Задачи и их решения с полной разборкой алгоритма.

Выпуск №1

Здравствуйте Дорогие подписчики! Сегодня я, Горшков Василий, начинаю свою первую рассылку. Не судите строго. Рассылка моя об олимпиадах по программированию. Всё очень просто, раньше я сам был участником олимпиад по программированию, мне это ужасно интересно. Думаю любой из Вас, читающих данную рассылку, и имеющий хотя бы какое то представление о программировании и об олимпиадах, найдет в этой рассылке, что-то своё - родное.

Вы, наверное, спросите: "А ТЫ САМ ИМЕЕШЬ ПРЕДСТАВЛЕНИЕ О ПРОГРАММИРОВАНИИИ??? И МОЖЕШЬ ЛИ ТЫ САМ ПРОГРАММИРОВАТЬ???". Отвечу честно, себя профессионалом никогда не считал. И считать не собираюсь, но : Дело в том, что я с седьмого класса занимаюсь подобными вещами и имею небольшой опыт в выступлении на олимпиадах. В школьные годы я даже выигрывал серебро на Туркменской государственной олимпиаде. Но дело не в этом, я не собираюсь хвастаться и кому то, что то доказывать, я просто хочу помочь тем, кто хочет научиться программировать, тем кому не хватает уверенности в решении каких то задач. Лично моё мнение, НАСТОЯЩИЙ ПРОГРАММИСТ РОЖДАЕТСЯ В СОПЕРНИЧЕСТВЕ, на олимпиадах, когда просыпается инстинкт быть ПЕРВЫМ! Так что смелее, Друзья, смелее. Я когда-то сам прошел через это, и одно время мне даже бросить хотелось, потому что было ужасно трудно, но вскоре все стало получаться и в итоге я уже сам публикую эту рассылку. Поэтому в этой рассылке я предлагаю дорогим читателям, задачи, а так же их решения. Все решения, будучи предоставлены в рассылке, составлены именно мной. Сами задачи по программированию, я, конечно, накачал из РУНЕТА.

Любой желающий, может мне присылать свои решения, а так же свои задачи, я их с удовольствием опубликую в одном из номеров. Решения желательно присылать на Паскале, Бейсике, либо С. Дело в том, что я владею пока только этими языками :) Все свои решения буду публиковать на Паскале.

В рассылке я собираюсь не только писать задачки и их решения, а так же подробно рассматривать алгоритм решения этой задачи. Поэтому, я думаю, даже начинающим программистам следует подписаться на эту рассылку, не знающим даже азов программирования.

Итак, задача сегодняшнего номера:

Ближайшее большее

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

Например: N=123 Ответ: 132

На первый взгляд задача вроде проста, но, немного подумав, я пришел к выводу, что не так уж это и просто, как кажется на первый взгляд. Важно правильно понять задачу и всё заранее продумать. Со мной был как-то случай на олимпиаде: по своей невнимательности и неопытности, прочитав задание и не вникнув в него до конца, начал делать его. Вроде сделал, но в итоге, когда дело дошло до проверки моего задания, решение оказалось неверным и в итоге я не получил ни одного балла :) (простите, что-то я отклонился от темы)

Рассмотрим задачу: задача на первый вид вроде проста, можно все организовать одним циклом и ни каких проблем. Но есть одна загвоздка, "количество цифр не должно превышать 80", т.е. числа очень большие, явно не попадают в диапазон Integer и Longint, следовательно, обычным циклом организовать не удастся.

Я пытался найти какую то закономерность, чтобы не использовать циклы, но увы у меня это не получилось. Может у Вас это получится??? Можете присылать свои примеры, как бы Вы решили данную задачу ко мне на ящик.

Поэтому я решил использовать просто массив, массив из 80 чисел. Сначала запросить строку, якобы число. После чего эту строку разбить на символы (цифры) и распределить в массив. Далее идет самое сложное в этой задаче: организовать цикл в этом массиве.

Я решил сделать это при помощи рекурсивной процедуры. В рекурсивной процедуре я увеличиваю N-ый элемент на один и в случае если N-ый элемент равен 10 проделываю тоже самое с N-1 элементом.

Далее же просто сравниваю суммы цифр начального массива и текущего, в случае равенства заканчиваю программу, выводя на экран ответ. Всё просто :)

Прочитав этот код, Вы скорее всего спросите: А ЗАЧЕМ ВООБЩЕ НУЖНА ПРОВЕРКА НА N=0???

Итак, как работает мой цикл???

Допустим, что ввели строку (число) "98". Заполнится массив следующим образом:

A[1]='9'; A[2]='8';

Что будет делать моя программка??? Она будет увеличивать последний элемент. Т.е. после первого шага массив будет выглядеть следующим образом:

A[1]='9'; A[2]='9';

А что же дальше??? Дальше, если не использовать проверку N на ноль, программа обнулит второй элемент и первый элемент. А дальше выдаст ошибку, потому что начнет обращаться к N-1 элементу, в данном случае он будет нулевой. Выдаст ошибку, не так ли???

Для этого и предусмотрена эта проверка, она увеличивает количество элементов в массиве и обнуляет все элементы, кроме первого. Первому же присваивает единицу.

Ниже приведен исходный текст программы: 


uses crt;
var err,i,m,sum:integer;
    a:array[1..80] of integer;
    s:string;

procedure recurs(n:integer);
var sum2,i:integer;
begin
 if n=0 then begin
  m:=m+1;
  a[1]:=1;
  for i:=2 to m do a[i]:=0;
  n:=m;
 end else inc(a[n]);
 sum2:=0;
 if a[n]=10 then begin
  a[n]:=0;
  recurs(n-1);
 end;
 for i:=1 to m do sum2:=sum2+a[i];
 if sum2<>sum then recurs(m) else begin
  for i:=1 to m do write(a[i]);
  writeln;
  readkey;
  halt(1);
 end;
end;

begin
 clrscr;
 sum:=0;
 readln(s);
 i:=1;
 while(s[i]='0')and(i<length(s)) do inc(i);
 s:=copy(s,i,length(s));
 if s='0' then begin writeln('Таких чисел нет!'); readkey; halt(1); end;
 m:=length(s);
 for i:=1 to m do begin
  val(s[i],a[i],err);
  sum:=sum+a[i];
 end;
 recurs(m);
end.
Ну, вот, дорогие подписчики, на сегодня и всё. Надеюсь, объяснял всё довольно на доступном языке. Любые недовольства, либо восхищения (если конечно будут) по поводу рассылки и написанного здесь мной, можете присылать ко мне на ящик.

Так же жду от Вас писем с задачками или их решениями, всё присланное вами я опубликую в одном из номеров этой рассылки (если конечно решения будут верны).

Все номера рассылки, абсолютно бесплатно, можно скачать у меня на сайте: www.alleprogramming.yandex.ru

В избранное