Классические алгоритмы и игры на C# для школьников

Упражнение 1:

Номер 1

Какие  утверждения  справедливы  относительно  поиска  элемента  с  заданными  свойствами?

Ответ:

(1) Поиск элемента можно вести в два этапа. Вначале построить множество кандидатов, затем построить фильтр, выбирающий нужного кандидата;

(2) Лучшим методом поиска является метод "полного перебора" всех элементов множества;

(3) Для поиска иногда можно применять метод "полного перебора";

(4) Метод "случайного поиска" иногда может найти нужный элемент быстрее, чем другие методы.

Номер 2

Какие  утверждения  справедливы  относительно  простых  делителей  числа  N?

Ответ:

(1) Минимальный делитель N, больший единицы, является простым числом;

(2) При поиске минимального делителя нужно проверить все числа из интервала [3, N];

(3) При поиске минимального делителя нужно проверить все числа из интервала [3, N/2];

(4) Для поиска минимального делителя достаточно рассмотреть множество кандидатов – числа из интервала math

.

Номер 3

Какие  утверждения  справедливы  относительно  простых  чисел?

Ответ:

(1) Существует самое большое простое число;

(2) Множество простых чисел бесконечно;

(3) Плотность простых чисел убывает с ростом N.

Упражнение 2:

Номер 1

Метод  HowMuchDivisors(N)  в  качестве  результата  возвращает  число  всех  делителей  числа  N.  Какое  выражение  истинно,  когда  N  –  простое  число?

Ответ:

(1) HowMuchDivisors(N) == 0;

(2) HowMuchDivisors(N) == 1;

(3) HowMuchDivisors(N) == 2;

(4) HowMuchDivisors(N) > 2.

Номер 2

Метод  MinDivisor(N)  в  качестве  результата  возвращает  минимальный  делитель  числа  N,  больший  единицы.  Какое  выражение  истинно,  когда  N  –  простое  число?

Ответ:

(1) MinDivisor(N) == 3;

(2) MinDivisor(N) == 4;

(3) MinDivisor(N) == 5;

(4) MinDivisor(N) == N.

Номер 3

Чем  знаменит  Эратосфен?

Ответ:

(1) Предложил алгоритм вычисления простых чисел;

(2) Предложил алгоритм вычисления наибольшего общего делителя;

(3) Внес существенный вклад в основания науки "география";

(4) Измерил радиус земли.

Упражнение 3:

Номер 1

Какие  утверждения  справедливы  для  алгоритма  "Решето  Эратосфена"?

Ответ:

(1) Перебираются все нечетные числа и для каждого из них определяется, является ли оно простым;

(2) Числа в решете Эратосфена, которые не были "проколоты", являются простыми;

(3) Из решета удаляются (прокалываются) все числа, кратные последнему найденному простому числу;

(4) Эратосфен в качестве решета использовал восковую таблицу с нанесенными на ней числами.

Номер 2

Первый  ученый,  кто  нашел  все  простые  числа  в  первой  тысяче  чисел,  был:

Ответ:

(1) Архимед;

(2) Эратосфен;

(3) Эвклид.

Номер 3

Какие  утверждения  справедливы  относительно  алгоритма  поиска  всех  простых  чисел  в  интервале  [min, max],  где  min  >  2?

Ответ:

(1) Множеством кандидатов является множество нечетных чисел в интервале [min, max];

(2) Фильтром может быть функция IsPrime(N), определяющая является ли N простым числом;

(3) Этот алгоритм может быть эффективнее алгоритма "решето Эратосфена", у которого минимальное значение фиксировано;

(4) Для любого интервала [min, max] всегда существует хотя бы одно простое число.

Упражнение 4:

Номер 1

Чем  знаменит  Эвклид?

Ответ:

(1) Внес существенный вклад в основания науки "геометрия";

(2) Измерил радиус Земли ;

(3) Предложил эффективный алгоритм нахождения наибольшего общего делителя чисел N и M;

(4) Предложил эффективный алгоритм вычисления множества простых чисел.

Номер 2

Какое  определение  Наименьшего  Общего  Кратного  чисел  N  и  M  -  НОК(N, M)  является  правильным?

Ответ:

(1) наименьшее число d, которое является делителем одного из чисел N или M;

(2) число d, у которого делителями являются числа N и M;

(3) наименьшее число d, которое является делителем числа N и числа M;

(4) наименьшее число d, у которого делителями являются числа N и M.

Номер 3

Какое  определение  НОД(N, M)  является  правильным?

Ответ:

(1) наибольшее число d, которое является делителем одного из чисел N или M;

(2) число d, которое является делителем числа N и числа M;

(3) наибольшее число d, которое является делителем числа N и числа M;

(4) наибольшее число d, у которого делителями являются числа N и M.

Упражнение 5:

Номер 1

Чему  равен  наибольший  общий  делитель  чисел  54  и  90?

Ответ:

(1) 9;

(2) 15;

(3) 18;

(4) 27.

Номер 2

Чему  равен  наибольший  общий  делитель  чисел  35  и  105?

Ответ:

(1) 1;

(2) 5;

(3) 7;

(4) 21;

(5) 35.

Номер 3

Чему  равен  наибольший  общий  делитель  чисел  42  и  105?

Ответ:

(1) 1;

(2) 3;

(3) 7;

(4) 21;

(5) 42.

Упражнение 6:

Номер 1

Чему  равно  наименьшее  общее  кратное  чисел  54  и  90?

Ответ:

(1) 54;

(2) 90;

(3) 270.

(4) 450.

Номер 2

Какие  утверждения  справедливы  относительно  наибольшего  общего  делителя  двух  чисел  N  и  M,  когда  N  >  M?

Ответ:

(1) НОД(N, 0) = N;

(2) НОД(N, M) = НОД(M, N - M);

(3) НОД(N, M) = НОД(2*N, 2*M);

(4) НОД(N, M) = НОД(N%M, M).

Номер 3

Какие  утверждения  справедливы  относительно  наибольшего  общего  делителя  двух  чисел  N  и  M  –  НОД(N, M),  где  N  >  M?

Ответ:

(1) НОД(N, M) = НОДM, N);

(2) НОД(N, M) = НОДM, N - M);

(3) НОД(N, M) = НОД(2*N, 2*M);

(4) НОД(N, M) = НОД(N/M, M).

Упражнение 7:

Номер 1

Какие  утверждения  справедливы  относительно  НОД  чисел  N  и  M?

Ответ:

(1) НОД(N,M) = НОД(N, N);

(2) НОД(N,N ) = N;

(3) НОД(N,M) = НОД(N/2, M/2).

Номер 2

Чему  равно  наименьшее  общее  кратное  чисел  35  и  105?

Ответ:

(1) 35;

(2) 105;

(3) 4410;

(4) 210.

Номер 3

Чему  равно  наименьшее  общее  кратное  чисел  42  и  105?

Ответ:

(1) 42;

(2) 105;

(3) 4410;

(4) 210.

Упражнение 8:

Номер 1

Для  возведения  числа  x  в  целую  степень  n?

Ответ:

(1) Необходимо выполнить n – 1 операций умножения;

(2) Достаточно выполнить Log(N) умножений, где функция Log возвращает двоичный логарифм числа n, округленный в большую сторону до ближайшего целого;

(3) Достаточно выполнить 2 * Log(N) умножений, где функция Log возвращает двоичный логарифм числа n, округленный в большую сторону до ближайшего целого.

Номер 2

Какие  утверждения  справедливы  для  программы,  вычисляющей  числа  -  градины?

Ответ:

(1) Существует такое число N, при котором цикл не завершается.

(2) Известно, что цикл while в этой программе всегда заканчивает работу;

(3) Доказательства того, что цикл while всегда заканчивается для любого начального значения n, пока не найдено.

Номер 3

Чему  равны  наибольший  общий  делитель  и  наименьшее  общее  кратное  для  чисел  15  и  36?

Ответ:

(1) 3 и 15;

(2) 6 и 72;

(3) 3 и 180;

(4) 5 и 180.

Упражнение 9:

Номер 1

Каково  минимальное  число  умножений  необходимо  выполнить  для  возведения  числа  x  в  степень  n  =  15?

Ответ:

(1) 15;

(2) 14;

(3) 8.

(4) 7.

Номер 2

Каково  минимальное  число  умножений  необходимо  выполнить  для  возведения  числа  x  в  степень  n  =  16?

Ответ:

(1) 15;

(2) 4;

(3) 8.

(4) 7.

Номер 3

Каково  минимальное  число  умножений  необходимо  выполнить  для  возведения  числа  x  в  степень  n  =  21?

Ответ:

(1) 15;

(2) 4;

(3) 8.

(4) 7.

Упражнение 10:

Номер 1

Сколько  раз  будет  выполняться  тело  цикла  в  алгоритме,  вычисляющем  числа  –  градины  при  начальном  значении  n  =  9?

Ответ:

(1) 9.

(2) 18.

(3) 19

(4) 2017

Номер 2

Сколько  раз  будет  выполняться  тело  цикла  в  алгоритме,  вычисляющем  числа  –  градины  при  начальном  значении  n  =  20?

Ответ:

(1) 9.

(2) 18.

(3) 19

(4) 20.

Номер 3

Сколько  раз  будет  выполняться  тело  цикла  в  алгоритме,  вычисляющем  числа  –  градины  при  начальном  значении  n  =  7?

Ответ:

(1) 9.

(2) 16.

(3) 19

(4) 20.

Классические алгоритмы и игры на C# для школьников - тест 10