Определение количества цифр числа

Kol N

1 12345

2 12345 div10 = 1234

3 1234 div10 = 123

4 123 div10 = 12

5 12 div10 = 1

1 div10 = 0

Определение текущей цифры числа

i Число М

1 12345

2 12345 div10 = 1234

3 1234 div10 = 123

4 123 div10 = 12

5 12 div10 = 1

 

Если цифры числа известны, определить наибольшую из них не составит руда. Алгоритм поиска максимального значения в некоторой последовательности цифр заключается в следующем. В ячейку, в которой будет храниться максимальный элемент (max), записывают значение, меньшее любого из элементов последовательности (в нашем случае max = -1, так как цифры числа находятся в диапазоне от 0 до 9). Затем сравнивают элементы последовательности си значе­нием ячейки max, если найдется элемент, превышающий значение предполагае­мого максимума, то ячейке max необходимо присвоить значение этого элемента и, соответственно, запомнить его номер в последовательности (в нашем случае переменной pos присваивается значение параметра цикла). В алгоритме поиска минимума вначале в переменную min записываем значение, заранее боль­шее любого элемента последовательности. Затем все элементы последовательности сравниваем с win. Если встретится значение меньшее, чем min, переписываем его в переменную min.

 

Текст программы

var M,N,max:longint;

i,kol,pos:word;

Begin

{ Так как речь идет о натуральных числах, }

{ при вводе предусмотрена проверка. }

{ Закончить цикл, если введено положительное число, }

{ иначе повторить ввод. }

Repeat

write (‘N=’); readln (N);

until N>0;

M:=N; { Сохранить значение переменной N. }

kol:=l; { Предположим, что число состоит из одной цифры. }

while M div 10 > 0 do {Выполнять тело цикла, пока число делится нацело на 10. }

Begin

kol:=kol+l; { Счетчик количества цифр. }

М:=М div 10; { Изменение числа. }

end;

max:=-1; { Присвоение максимуму начального значения. }

pos:=l; { Предполагаемая позиция максимума в числе. }

M:=N;

For i:=kol downto 1 do { Нумерация цифр в числе слева}

Begin

if M mod 10 > max then { Если цифра больше предполагаемого максимума, то }

Begin

max:=M mod 10; { заменить максимум этой цифрой }

pos:=i; {запомнить 'ее позицию в числе}

end;

М:=М div 10; {изменение числа. }

end;

writeln ('max=',max,' pos=',pos);

End.

Пример 4. Определить количество простых чисел в интервале от N до М, де N и М - натуральные числа.

 

 

 

 

 

Пример 5. Вводится последовательность целых чисел, 0-е конец. Найти минимальное среди положительных значений; если их несколько, определить количество.

Заметим, что логическая переменная Pr определяет наличие положительных чисел в последовательности (Pr = false, если положительных чисел нет)

 

Блок – схема:

 

 

 

 

 

 

 

 

Текст программы:

var Блок-схема решения задачи

min, n, k: integer;

pr:boolean;

Begin

{Вводим первое число последовательности}

write ('N='); readln (N);

{Предполагаем, что в последовательности нет положительных значений}

pr:=false;

{Количество минимумов равно 0}

к:=0;

{Если текущее значение не равно 0, то входим в цикл}

while (N<>0) do

Begin

if N>0 then { Если число положительное проверяем, если это первое положительное число}

if not Pr then

Begin

Pr:=true; { в последовательности есть положительные числа, }

min:=N; { первое положительное число записываем в переменную min}

end { количество минимумов =1. }

else { Если это не первое положительное число, }

if min>N then { если число меньше min, }

Begin

min:=N; { то его переписываем в переменную min, }

k:=l { количество минимумов =1. }

End

else { Если текущий элемент последовательности равен min, количество минимумов

if min=N then k:=k+l; {увеличиваем на 1 }

 

write ('N='); readln (N); { Вводим очередное значение последовательности. }

end; I

if Pr then

writeln ('min=',min,'. Количество минимумов =',k)

else

writeln t ('Отсутствуют положительные элементы.');

End.

 

-

! Существует класс задач, в которых из некоторого количества вариантов необходимо выбрать наиболее подходящий (оптимальный). Для таких задач далеко не всегда удается найти алгоритм, который позволил бы получить ре­шение без анализа всех или большого количества комбинаций исходных дан­ных, т.е. без осуществления перебора. Осуществление полного перебора тре­бует много времени. Вычислительная сложность решения задач с использо­ванием перебора обычно оценивается как О(n!) или даже О(nⁿ).

Для решения задач данного типа применяют две стратегии:

• формируют сразу всю комбинацию исходных данных и выполняют ее
анализ в целом;

• генерацию и анализ комбинации осуществляют по частям.

Если имеется возможность, анализируя часть комбинации исходных данных, оценить ее перспективность с точки зрения получения решения, то вторая стратегия позволит получить результат за меньшее время за счет ис­ключения из рассмотрения всех комбинаций, в которые входит данная часть. Исключение бесперспективных комбинаций {отсечение вариантов) позволя­ет осуществить не полный, а ограниченный перебор.

 

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

Общий алгоритм решения задачи с использованием полного перебора по первой стратегии может быть представлен следующим образом.

Цикл-пока еще есть варианты

Генерировать комбинацию исходных данных

если вариант удовлетворяет условию,

то Обработать вариант

все-если

Все-цикл