Министерство образования и науки Российской Федерации 4 страница. Проверим, является ли число 255 совершенным

Проверим, является ли число 255 совершенным. Число 1 является делителем любого числа, поэтому сразу можно поместить в переменную s значение 1; 255 - нечётное число, следовательно, оно не имеет чётных делителей, так что будем искать делители только среди нечётных чисел. 255 делится на 3, значит оно имеет ещё один делитель – 255 / 3 = 85; s = 1+ 3 + 85 + ... Cледующая пара делителей - 5 и 51: s = 1 + 3 + 85 + 5 + 51 +... Точно так же находим ещё два делителя - 15 и 17. Следующий делитель 17 у нас уже есть, перебор прекращается, s = 1 + 3 + 85 + 5 + 51 + 15 + 17 = 177 < 255, число 255 не является совершенным.

Теперь проверим, является ли совершенным число 16: это число чётное, оно делится на 2 и 4, 16 / 2 = 8, 16 / 4 = 4, два делителя совпадают, поиск делителей прекращается.

Обобщая наши исследования, можно сказать, что в том случае, когда число p является делителем числа q, то q делится без остатка на q / p, один из этих делителей не превосходит корня квадратного из q, а другой не меньше этого значения. Следующий макет программы выглядит так:

Макет № 4

/*perfnum4.c*/

/*программа читает числа a,b, содержащиеся в тестовом файле и выводит на экран все совершенные числа, заключённые между a и b*/

#include <math.h> /*заголовочный файл math.h содержит описания математических функций */

#include <stdio.h> /*файл содержит описания средств ввода-вывода*/

main()

{

int a, b;

int i, j, k,s;

int p, q;

float m;

scanf ( " a = %d b = %d", &a, &b);

if ( b < 6 )

{

printf ("NO PERFECT NUMBERS\n");

return 0;

}

if ( a % 2 ==0 ) // Если a чётное число

{ p = a; q = a+1; }

else

{ q = a; p = a +1; }

for ( i = p; i <= b; i = i+2 )

{ // перебираем чётные числа, заключённые между a и b

s = 1; //инициализация сумматора s

m = sqrt ( i ) + 1; // будем искать те делители числа i, которые не превосходят корня квадратного из i

for ( j = 2; j <= m ; j++)

if ( i % j == 0)

{

s+= j;

if ( (k = i / j) < j) s+= k;

}

/* После завершения цикла значение переменной s равно сумме всех делителей числа i */

if ( i == s)

printf ("%d ", i);

}

for ( i = q; i <= b; i = i + 2 )

{ // перебираем нечётные числа, заключённые между a и b

s = 1; //инициализация сумматора s

m = sqrt ( i ) + 1; // будем искать те делители числа i, которые не превосходят корня квадратного из i

for ( j = 3; j <= m; j = j + 2) /*ищем только нечётные делители*/

if ( i % j == 0)

{

s+= j;

if ( (k = i / j) < j) s+=k;

}

/* После завершения цикла значение переменной s равно сумме всех делителей числа i */

if ( i == s)

printf ("%d ",i);

}

return 0;

}

Вычисление корня квадратного требует значительного времени, поэтому мы введём две целых переменных - m и sqm. Когда начинается выполнение программы, их значения равны, оответственно, (int)sqrt (a) + 1 и m * m. Как только i становится больше sqm, программа прибавляет к sqm 2 * m + 1 и увеличивает m на единицу. Таким образом, m равно наименьшему натуральному числу, квадрат которого больше i.

Макет № 5

/*perfnum5.c*/

#include <math.h> /*файл содержит описания математических функций */

#include <stdio.h> /*файл содержит описания средств ввода-вывода*/

main()

{

unsigned int a,b;

unsigned int i, j, k,s;

unsigned int p,q;

unsigned int m, sqm;

scanf ( " a = %d b = %d", &a, &b);

if ( b < 6 )

{

printf ("NO PERFECT NUMBERS\n");

return 0;

}

if ( a % 2 ==0 ) // Если a чётное число

{ p=a; q=a+1; }

else

{ q=a; p=a+1; }

m = (int) sqrt (p) + 1; sqm = m * m;

for (i = p; i <= b; i = i+2 )

{ // перебираем чётные числа, заключённые между a и b

s = 1; //инициализация сумматора s

for ( j = 2; j <= m ; j++)

if ( i % j == 0 )

{

s+= j;

if ( ( k = i / j) < j ) s+= k;

}

/* После завершения цикла значение переменной s равно сумме всех делителей числа i */

if ( i == s )

printf ("%d ",i );

}

m = (int)sqrt ( q ) + 1; sqm = m * m;

for ( i = q; i <= b; i = i + 2 )

{ // перебираем нечётные числа, заключённые между a и b

s = 1; //инициализация сумматора s

for ( j = 3; j <= m ; j = j + 2) /*ищем только нечётные делители*/

if ( i % j == 0)

{

s+= j;

if ( ( k = i / j ) < j ) s+=k;

}

/* После завершения цикла значение переменной s равно сумме всех делителей числа i */

if ( i == s)

printf ("%d ",i);

}

return 0;

}

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

Дальнейшие преобразования программы perfnum.c не оказывают влияния на объём ресурсов, которые она использует, но изменяет её стиль. Завершаясь, программа всегда должна сообщать результат решения задачи, тогда как perfnum5.c ничего не выводит на экран, когда между a и b нет совершенных чисел. Мы введём переменную flag - флаг, такая переменная содержит информацию о состоянии выполняющейся программы. Если программа не обнаружила совершенных чисел, то её значение равно NO ( 0 ), если найдено хоть одно совершенное число, её значение становится равным YES ( 1 ). Кроме того, программа содержит два почти одинаковых фрагмента, а хороший стиль требует, чтобы в ней не было повторений. Поэтому мы добавим ещё один цикл. Начиная с макета № 1 мы старались в группировать объявления переменных, так чтобы в одном объявлении были собраны переменные, выполняющие общую функцию. Точно так же пропуски строк помогают разбить программу на отдельные блоки.

Макет № 6 (незавершённый)

/*perfnum6.c*/

#include <math.h> /*файл содержит описания математических функций */

#include <stdio.h> /*файл содержит описания средств ввода-вывода*/

#define NO_NUMBERS "NO PERFECT NUMBERS BETWEEN a=%d b=%d \n"

#define NO 0

#define YES 1

main()

{

unsigned int a, b;

unsigned int i, j, k, r, d, s;

unsigned int p, q;

unsigned int m, sqm;

unsigned int flag = NO;

scanf ( " a = %d b = %d", &a, &b);

if ( b < 6 )

{

printf (NO_NUMBERS. a, b);

return 0;

}

if ( a % 2 ==0 ) // Если a чётное число

{ p = a; q = a + 1; }

else

{ q = a; p = a + 1; }

m = (int) sqrt ( p ) + 1 и sqm = m * m;

d=1;

for ( r = 0 ; r <= 1; r++)

{

for ( i = p; i <= b; i = i + 2)

{ /* при первом проходе цикла перебираем чётные числа, заключённые между a и b, при втором - нечётные */

s = 1; //инициализация сумматора s

for ( j = 2; j < sqrt (i) + 1; j = j + d)

if ( i % j == 0)

{

s+=j;

if ( (k = i / j) < j) s+=k;

}

/* После завершения цикла значение переменной s равно сумме всех делителей числа i */

if ( i == s)

{ printf ("%d ",i); flag = YES; }

}

m = (int)sqrt (q) + 1 и sqm = m * m;

d = 2;

p = q;

}

if ( NO == flag )

printf (NO_NUMBERS, a, b);

return 0;

}

ЗАДАЧИ

1-я неделя

Составьте программу сортировки массива. Методы сортировки:

выбором;

пузырьком;

вставками;

слиянием.

Составьте программу двоичного поиска значения элемента упорядоченного массива.

Составьте программы, которые выводят на экран:

все перестановки элементов массива;

все подмножества множества значений элементов массива;

все наборы заданной длины, составленные из заданных букв.

составьте программу для решения задачи о восьми ферзях.

2-я неделя

1 На вход программы поступает натуральное число n, программа находит наименьшее число, которое можно представить в виде суммы квадратов n натуральных чисел по крайней мере двумя способами.

2 На вход программы поступает натуральное число p; программа выводит в порядке возрастания все правильные несократимые дроби, знаменатели которых не превосходят p. Примечание. Порядок объёма оперативной памяти, которую использует программа, не должен превосходить p.

3 На вход программы поступает натуральное число n, программа выводит все представления n в виде суммы натуральных чисел. Представления, отличающиеся порядком слагаемых, считаются тождественными.

4 На вход программы поступает матрица порядка m*n, элементами которой служат целые положительные числа; программа выдаёт те числа, которые содержатся в каждой строке матрицы. Предполагается, что в оперативной памяти можно разместить лишь ограниченное количество строк матрицы.

5 Пусть P=(p1, p2, ..., pn) - перестановка натуральных чисел 1,2,...,n. Набор m1,m2,...,mn называется таблицей инверсий этой перестановки, если для любого i=1,2,...,n mi равно количеству чисел, которые больше i, но в перестановке P стоят раньше, чем i. На вход программы поступает поступает набор n натуральных чисел. Программа определяет, может ли она быть таблицей инверсий какой-либо перестановки и выводит эту перестановку.

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

7 На вход программы поступают натуральные числа n, k. Программа выводит на экран набор, состоящий из n нулей и единиц, в котором никакой фрагент не повторяется k раз подряд, или сообщает об отсутствии такого набора.

8 Описание игры. Двое игроков поочерёдно называют натуральные числа a1, a2,... Число a1 не превосходит заданного натурального числа a, для любых k = 1, 2,... разность мжду числами a(k+1), ak положительн и не превосходит a. Выиграет тот игрок, который первым назовёт число b.

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

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

bcc32 – M -компоновщик(???) создаёт файл с расширением map, содержащий информацию о распределении памяти;

bcc32 – S -компилятор создаёт файл с расширением asm, содержащий команды объектного файла, записанные на языке Ассемблер;

bcc32 – c -компилятор создаёт объектный файл (с расширением obj), но не вызывает компоновщика;

bcc32 – o имя_исполняемого_файла (???) -компоновщик создаёт исполняемый файл (с расширением exe), с заданным именем.

{public void paint (Graphics g)

{

Font font = new Font («TimesRoman», FontBOLD, 24);

g.setFont ( font );

g.drawString («I am a student», 5, 25)

}

В переменную окружения Path добавить: C:\ProgramFiles\Java\jdk 1.6.0_18

–