Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление)



Скачать 28.65 Kb.
Дата30.11.2012
Размер28.65 Kb.
ТипРешение
2. Решение задач на условие делимости чисел
При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление).

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

Рассмотрим несколько примеров.
2.1. (Улусная олимпиада 2008 г.) Найти все делители натурального числа N. Входные данные: натуральное число N, выходные данные: все делители числа N. Например:

input.txt

output.txt

18

1 3 6 9 18


Обозначения:

n – исходное натуральное число

d – делители числа
Алгоритм решения задачи:

  1. Перебор всех делителей (натуральных чисел) от 1 до n

  2. Проверка условия: делится ли n на d без остатка

  3. Если условие выполняется, то выводим делитель d в выходной файл


Здесь уместно использовать безусловный цикл (for), т.к. при невыполнении условия никаких действий не совершается.
Задание: Запишите алгоритм в виде блок-схемы.
Решение:

program z2_1;

var f1, f2: text;

n,d: integer;

begin

assign (f1, 'input.txt'); reset (f1);

assign (f2, 'output.txt'); rewrite (f2);

read (f1,n);

for d:=1 to n do if n mod d = 0 then write (f2, d,' '); {после переменной выводим пробел для разделения делителей}

close (f1); close (f2);

end.
Возможно ли вместо условия n mod d = 0 воспользоваться условием равенства обычного деления и целочисленного деления: n/d=n div d ?

2.2. (Улусная олимпиада 2009 г.) Составить программу, определяющую простое ли число X. Входные данные: число Х, выходные данные: слово «простое» или «составное». Например:

input.txt

output.txt

17

простое


Обозначения:

х – входное число

d – делители

k – счетчик количества делителей
Идея решения: перебор делителей от 1 до х, если количество делителей равно 2 (т.е. 1 и само число), то число простое, в противном случае – составное.

Запишите алгоритм решения в виде блок-схемы.
Решение:

program z2_2;

var f1, f2: text;

x,d,k: integer;

begin

assign (f1, 'input.txt'); reset (f1);

assign (f2, 'output.
txt'); rewrite (f2);

read (f1,x);

k:=0;

for d:=1 to x do if x mod d = 0 then k:=k+1;

if k=2 then write (f2, 'prostoe') else write (f2,'sostavnoe');

close (f1); close (f2);

end.
Алгоритм такого решения имеет недостаток - производится перебор всех делителей, даже если количество делителей уже стало больше 2-х.

Попробуйте дать учащимся решить, исключив этот недостаток. Указание: используйте цикл с условием while ... do...
Решение:

program z2_2_1;

var f1, f2: text;

x,d,k: integer;

begin

assign (f1, 'input.txt'); reset (f1);

assign (f2, 'output.txt'); rewrite (f2);

read (f1,x);

k:=0; {при повторном запуске программы k принимает начальное значение, т.к. в памяти остаются последние значения переменных}

d:=1; {аналогично}

while ((d<=x) or (k<2)) do {пока d<=x или k<2 выполняем}

begin

if x mod d = 0 then k:=k+1;

d:=d+1;

end;

if k=2 then write (f2, 'prostoe') else write (f2,'sostavnoe');

close (f1); close (f2);

end.
Задачи для самостоятельного решения
2.3. (Улусная олимпиада 2001 г.) Дано натуральное число N. Найти все его простые делители. Входные данные: натуральное число N, выходные данные: все простые делители числа N. Например:

input.txt

output.txt

17

простое


Задача включает в себя решение задач 2.1 и 2.2.

2.4. Совершенное число – число равное сумме своих делителей (не считается делителем числа само число). Найти все совершенные числа до N.

Входные данные: натуральное число N, выходные данные: все совершенные числа до N. Например:

input.txt

output.txt

100

6 28


2.5. (Улусная олимпиада 2007 г.) Найти наибольший общий делитель (НОД) двух чисел. Входные данные: натуральные числа m и n, выходные данные: наибольший общий делитель nod

Например:

input.txt

output.txt

276 672

12

Похожие:

Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) iconТипы данных: Целый тип
Над целыми значениями допустимы следующие операции: +, -, *, / и дополнительные операции типа "деления": div деление нацело (с отбрасываемой...
Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) iconМетодика определения делимости чисел натурального числового ряда и ее практическое применение
На основании использования вспомогательных числовых рядов по mod 6 и по mod 4 из натурального ряда чисел вычленены составные числа...
Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) iconРешение задач на последовательности При решении таких задач бывает необходимо: каким-либо образом сортировать последовательности
Прежде всего рассмотрим общую структуру программы при решении задач на обработку последовательности чисел (массивов) на примере заполнения...
Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) iconРешение геометрических задач по планиметрии
При решении большинства задач не обойтись без привлечения разнообразных фактов теории доказательств тех или иных утверждений. Но...
Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) icon«Признаки делимости в различных системах счисления»
Данная работа посвящена исследованию признаков делимости в различных системах счислениях. Здесь рассматриваются признаки делимости...
Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) iconОбобщение знаний по теме «Делимость чисел»
«Делимости чисел». Кто живет в этой стране? Вы, наверное, догадались: множество натуральных чисел, признаки делимости. А правят этой...
Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) iconРешение задач со строковыми переменными При решении таких задач бывает необходимо: найти определенные символы (цепочки символов) поиск, подсчет
Для решения задач со строковыми переменными необходимо уметь «вырезать» часть строковой переменной (слов), подсчитывать длину строковых...
Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) iconМатематика, 8 класс
Критерий, устанавливающий необходимое и достаточное условие делимости произвольного натурального числа n на данное натуральное число...
Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) iconII. Алгоритмы. Применение теоремы делимости к решению уравнений. Схема Горнера
Теорема Безу дает возможность, найдя один корень многочлена, искать далее корни многочлена, степень которого на 1 меньше. При решении...
Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) iconУмножение и деление на Четверть числа. ( У м к начальная школа 21 века )
Закрепить знания табличного умножения и деления на 2, на 3; отрабатывать таблицу умножения и деления на 4, умения применять эти навыки...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org