4.2. Арифметические задач. Поиск решения линейным перебором

«В учебных задачах результат выполняемых
действий сам по себе обычно непривлекателен».

Л.Венгер, А.Венгер. Готов ли ваш ребенок к школе?

Задачи, основанные на свойствах чисел, составляющих их цифр – излюбленная тематика школьных олимпиад по программированию. Достоинство их в том, что ничто лишнее не мешает созерцать принципы проектирования программ, стандартные программные контексты, да и стыдно ссылаться на незнание арифметики.

Свойства делимости. Такие арифметические процедуры как сокращение дробей, разложение числа на простые множители, определение наименьшего общего кратного, наибольшего общего делителя, поиск простых чисел и т.д. основаны на проверке свойств делимости чисел. Для этой цели используется операция получения остатка от деления «%», число делится на другое число, если остаток от деления равен 0. Нелишне напомнить, что все эти свойства определены для целых чисел, которым в Си соответствуют базовые типы данных int и long.

Работа с цифрами числа. То, что при выводе результата и при написании констант мы наблюдаем число, состоящее их цифр, еще ничего не значит, ибо это есть внешняя форма представления числа (см. 4.4). Когда мы используем целую переменную, она представлена в памяти во внутренней (двоичной) форме (1.3). То, что с этой формой компьютером выполняются арифметические действия, можно считать «чудом» и не вникать, как он это делает. Отдельные же цифры числа можно получить, используя правила составления числа из цифр в позиционной системе счисления: вес следующей цифры десятичного числа в 10 раз больше текущей. Тогда остаток от деления числа n на 10 можно интерпретировать как значение младшей цифры числа, частное от деления на 10 – как отбрасывание младшей цифры числа, из чего составляется простой цикл получения цифр числа в обратном порядке. Выражение s10 «дописывает» к числу 0 справа, а s = s10 + k добавляет к нему очередную цифру k.

Поиск полным перебором. Когда речь идет о поиске решения, не стоит забывать, что кроме оригинальных алгоритмов всегда существует «тупой» способ последовательно перебирать все возможные значения, пока не наткнемся на нужное. Возможно, что он будет работать значительно медленнее, но все же приемлемо для наших входных данных. Все арифметические задачи, ребусы, головоломки и т.д. могут решаться путем линейного перебора всех возможных значений чисел с выделением всех, либо первого подходящего варианта. Как правило, такой цикл является внешним в программе поиска. Для поиска первого подходящего проверяемое условие может быть вынесено в заголовок цикла, но только в инверсном виде, поскольку любой цикл имеет в заголовке условие продолжения. Для поиска наименьшего из возможных перебор нужно производить в направлении увеличения проверяемых значений, для поиска наибольшего - в направлении уменьшения. Рассмотрим несколько простых примеров.

Счастливые билеты. «Счастливым» называется билет, в котором в шестизначном номере сумма первых трех цифр равна сумме последних трех. Решение строится на основе полного перебора всех шестизначных чисел. Каждое из них следует разложить на цифры, а затем сравнить суммы первых и последних трех. Как видим, решение складывается из стандартных фрагментов, нужно только выложить их в нужной последовательности «сверху вниз».

1. Исходные данные и результат. Функция возвращает целое - количество «счастливых» билетов. Формальных параметров нет. Основа алгоритма – полный перебор возможных билетов, то есть всех шестизначных чисел. Если число «счастливое» - увеличивается счетчик. Для определения свойства «быть счастливым» число необходимо разложить на цифры. Если они будут записаны в массиве, то условие будет легко записано: сумма первых трех элементов массива равна сумме трех последних.

int happy() {
  int n;  // Количество «счастливых» билетов
  long v;  // Проверяемое шестизначное число
  int B[6];  // Массив значений цифр

  for (n = 0, v = 0; v <= 999999; v++) {
    // Разложить v в массив цифр числа - B
    if (B[0] + B[1] + B[2] == B[3] + B[4] + B[5])
      n++;
  }

  return n;
}

2. Цифры числа получаются уже известным нам циклом деления числа на 10 с сохранением остатков от деления на 10 в элементах массива (порядок не важен).

int m;  // Номер шага (цифры)
long vv;  // Исходное число

for (vv = v, m = 0; m < 6; m++) {
  B[m] = vv % 10;  // Остаток - очередная цифра
  vv = vv / 10;  // Частное становится делимым
}

3. Окончательный вариант.

//------------------------------------------------------42-01.cpp
//------Счастливые билеты
long happy() {
  int m, B[6];
  long v, vv, n;

  for (n = 0, v = 0; v <= 999999; v++) {
    for (vv = v, m = 0; m < 6; m++, vv /= 10)

      B[m] = vv % 10;

    if (B[0] + B[1] + B[2] == B[3] + B[4] + B[5])
      n++;
  }

  return n;
}

Простые множители. Сформировать в массиве последовательность простых множителей заданного числа, ограниченную значением 0. Простые множители числа - простые числа, произведение которых дает заданное число, например: 72 = 22233.

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

void mnog(int val, int A[], int n) {
  int i;  // Количество множителей
  int m;  // Значение множителя

  for (i = 0; не кончился массив и есть множители; i++) {  
    // Получить очередной множитель m
    A[i] = m;
  }

  A[i] = 0;
}  // Ограничить последовательность

2. Получение очередного простого множителя. Простой множитель -минимальное простое число, на которое исходное делится без остатка. Если оно найдено (m), то на следующем шаге цикла его нужно «исключить» из раскладываемого числа, то есть использовать вместо исходного числа val частное от деления его на m. Таким образом, для перехода к следующему шагу цикла нужно выполнить val = val / m. Процесс должен продолжаться пока val не обратится в 1.

void calc(int val, int A[], int n) {
  int m, i;

  for (i = 0; i < n - 1 && val != 1; i++) {
    // Получить минимальное простое число m, нацело делящее val
    val /= m;
    A[i] = m;
  }

  A[i] = 0;
}

3. Минимальный простой множитель определяется обычным перебором значений, начиная с 2, пока не обнаружится делящееся нацело. Добавив цикл поиска, получим окончательный вариант.

//------------------------------------------------------42-02.cpp
//------Простые множители числа
void calc(int val, int A[], int n) {
  int m, i;

  for (i = 0; i < n - 1 && val != 1; i++) {
    for (m = 2; val % m != 0; m++)
      ;

    val /= m;
    A[i] = m;
  }

  A[i] = 0;
}

Простые числа. Сформировать массив простых чисел, не превышающих заданное. Простое число - число, которое делится нацело только на 1 и на само себя.

1. Исходные данные и результат - формальные параметры функции - аналогичны предыдущему примеру. Сущность алгоритма состоит в проверке всех чисел от 2 до val и сохранении их в массиве, если они простые.

void calc(int val, int A[], int n) {
  int i;  // Номер очередного простого числа
  int m;  // Очередное проверяемое число

  for (i = 0, m = 2; i < n - 1 && m < val; m++) {
    if (m - простое число)
      A[i++] = m;
  }

  A[i] = 0;
}

2. Конкретизируем утверждение, что m - простое число. Во-первых, оно не делится ни на одно число в диапазоне от 2 до m/2 включительно. Во-вторых, что то же самое, оно не делится ни на одно простое число от 2 до m-1. Но эти простые числа накоплены предыдущими шагами цикла в массиве A от A[0] до А[i-1] включительно. Таким образом, число простое, если оно удовлетворяет условию всеобщности: не делится ни на один элемент массива от 0 до i-1. Используем стандартный контекст с прерыванием цикла по нарушению проверяемого условия (число делится нацело на элемент массива) и проверяем свойство всеобщности как условие нормального завершения цикла (достижение конца заполненной части массива).

int n;

for (n = 0; n < i; n++)
  if (m % A[n] == 0)
    break;  // Разделилось нацело

if (i == n) {
  ... m - простое число...
}

3. Окончательный вариант:

//------------------------------------------------------42-03.cpp
//-------Простые числа
void calc(int val, int A[], int n) {
  int i, m, k;

  for (i = 0, m = 2; i < n - 1 && m < val; m++) {
    for (k = 0; k < i; k++)

      if (m % A[k] == 0)
        break;

    if (i == k)

      A[i++] = m;
  }

  A[i] = 0;
}

Головоломки. Все головоломки с подбором цифр решаются единообразно. Перебираются все числа в диапазоне поиска, в тело цикла вписываются проверки всех ограничений, которые видны в условии задачи: совпадение цифр, обозначенных буквами, несовпадение цифр, обозначенных разными буквами, появление заданных цифр на заданных позициях. Все, что «просеивается» через эти ограничения, и является решением задачи.

Число 512 обладает замечательным свойством: сумма его цифр в кубе равна самому этому числу. Требуется найти все числа с подобным свойством. Алгоритм поиска основан на полном переборе значений проверяемого числа a. В теле цикла подсчитывается сумма его цифр – s, а затем проверяется условие sss==a, которое и соответствует проверяемому свойству.

//------------------------------------------------------42-04.cpp
//-------- Поиск числа, подобного 512 > (5+1+2)=8, 8 ^ 3= 512
void find() {
  int a, n, k, s;

  for (a = 10; a < 30000; a++) {
    for (n = a, s = 0; n != 0; n = n / 10) {
      k = n % 10;
      s = s + k;
    }

    if (a == s * s * s)
      printf("%d^3=%d\n", s, a);
  }
}

Пример проектирования программы решения числового ребуса

Этапы проектирования программы и содержание отчета:

1. Основные "идеи" алгоритма, словесное описание общих принципов решения задачи.

2. "Образная модель" - пример, изображающий процесс решения задачи для конкретного набора данных.

3. Внутреннее представление данных в программе, выбор "системы координат".

4. Список стандартных фрагментов и необходимых переменных (с указанием их "смысла" в программе)

5. Выстраивание текста программы из компонент п.4 с использованием технологии нисходящего пошагового структурного проектирования

6. Окончательный текст программы с комментариями

7. Результаты работы.

Числовой ребус: ВАГОН + ВАГОН = СОСТАВ

1. Основные "идеи" алгоритма Программа должна выполнять полный линейный (последовательный) перебор всех пятизначных чисел, раскладывать их на цифры, пропускать повторяющиеся, удваивать очередное число (для получения из ВАГОН - СОСТАВ), проверять на совпадение цифр, обозначенных буквами О,А,В, оригинальность цифр для букв С и Т.

2. Образная модель…

3. Внутреннее представление данных в программе. Есть два варианта представления данных: либо перебор каждой цифры отдельным циклом (соответственно, 5 вложенных циклов), либо разложение числа в диапазоне от 10000 до 99999 в массив цифр. Выбираем второй вариант.

4. Список стандартных фрагментов и необходимых переменных.

   4.1. Поскольку раскладывать число по цифрам потребуется 2 раза, реализуем этот процесс в виде функции (исходник взят из тестов к главе 2). – функция toDigit.

   4.2. Для проверки оригинальности цифр можно использовать массив признаков M, в котором проверяемая цифра является индексом. Для каждой цифры k проверяется M[k], если оно равно 0, то устанавливается в 1, иначе – обнаруживается повторение.

   4.3. По условию задачи диапазон проверки 10000…99999, но т.к. удвоенное число – шестизначное, то диапазон будет 50000…99999. Цикл перебора и переменная – проверяемое число.

   4.4. Проверяемое число (ВАГОН) раскладывается по цифрам в массив A1 вызовом функции toDigit

   4.5. Удвоенное число (СОСТАВ) раскладывается по цифрам в массив B1 вызовом функции toDigit

   4.6. Проверка условия – в слове СОСТАВ две буквы С – иначе пропуск

   4.7. Проверка условий – в слове СОСТАВ буквы О, А, В совпадают с аналогичными буквами в слове ВАГОН – иначе пропуск

   4.8. Проверка условия – в слове состав – оригинальная буква Т, не совпадает с С и нет в слове ВАГОН.

   4.9. Если все условия соблюдены – вывод проверяемого значения.

5. Выстраивание текста программы из компонент п.4 с использованием технологии нисходящего пошагового структурного проектирования

ШАГ0. Функция toDigit

int toDigit(int A[], int a) {
  //--------------------------------------------------------16
  int i, n;

  for (i = 0, n = a; n != 0; i++, n = n / 10);

  int k = i--;  // Количество цифр

  for (n = a; n != 0; i--, n = n / 10)
    A[i] = n % 10;  // Запись остатков в обратном порядке с конца

  return k;
}

ШАГ1.Пункт 4.3 - цикл

void main() {
  int vv;  // Проверяемое число

  for (vv = 50000; vv <= 99999; vv++) {  // Перебор диапазона 5-значных чисел
    // Проверить vv
  }
}

ШАГ2. Пункт 4.3 – тело цикла – последовательность

void main() {
  int vv;  // Проверяемое число

  for (vv = 50000; vv <= 99999; vv++) {  // Перебор диапазона 5-значных чисел
    // 4.4 Разложение ВАГОН по цифрам
    // 4.2 Проверка повторений (с пропуском)
    // 4.5 Разложение СОСТАВ по цифрам
    // 4.6 в слове СОСТАВ две буквы С – иначе пропуск
    // 4.7 буквы О, А, В совпадают с аналогичными буквами в слове ВАГОН – иначе
    // пропуск

    // 4.8 в слове состав – оригинальная буква Т, не совпадает с С и нет в слове
    // ВАГОН
    // 4.9 вывод проверяемого значения
  }
}

ШАГ3. Пункты 4.4,4.5,4.9 – разложение по цифрам и вывод

void main() {
  int vv;  // Проверяемое число

  for (vv = 50000; vv <= 99999; vv++) {  // Перебор диапазона 5-значных чисел
    int A1[10], B1[10];  // Разложение по цифрам ВАГОН и СОСТАВ
    toDigit(A1, vv);  // Разложение ВАГОН

    // 4.2 Проверка повторений (с пропуском)
    toDigit(A1, vv);  // Разложение СОСТАВ
    // 4.6 в слове СОСТАВ две буквы С – иначе пропуск
    // 4.7 буквы О, А, В совпадают с аналогичными буквами в слове ВАГОН
    // 4.8 в слове состав – оригинальная буква Т, не совпадает с С и нет в слове
    // ВАГОН

    printf("%d+%d=%d\n", vv, vv, 2 * vv);
  }
}

ШАГ4. Пункт 4.2 – проверка цифр на оригинальность

int M[10];  // Массив признаков = цифра БЫЛА

for (int j = 0; j < 10; j++)
  M[j] = 0;  // Очистить массив признаков

int retr = 0;  // Признак - повторение цифры

for (int j = 0; j < 5; j++) {
  int k = A1[j];  // Очередная цифра

  if (M[k] != 0) {  // Цифра уже была
    retr = 1;
    break;
  } else
    M[k] = 1;  // Отметить, что была
}

if (retr)
  continue;  // Повторение цифр – к следующему шагу

ШАГ5. Пункты 4.6-4.8 – проверка условий

6. Окончательный текст программы с комментариями

#include <stdio.h>

int toDigit(int A[], int a) {
  //--------------------------------------------------------16
  int i, n;

  for (i = 0, n = a; n != 0; i++, n = n / 10);

  int k = i--;  // Количество цифр

  for (n = a; n != 0; i--, n = n / 10)
    A[i] = n % 10;  // Запись остатков в обратном порядке с конца

  return k;
}

void main() {
  int vv;  // Проверяемое число
  int A1[10], B1[10];  // Разложение по цифрам ВАГОН и СОСТАВ
  int M[10];  // Массив признаков = цифра БЫЛА

  for (vv = 50000; vv <= 99999; vv++) {  // Перебор диапазона 5-значных чисел
    toDigit(A1, vv);  // Разложение ВАГОН

    for (int j = 0; j < 10; j++)
      M[j] = 0;  // Очистить массив признаков

    int retr = 0;  // Признак - повторение цифры

    for (int j = 0; j < 5; j++) {
      int k = A1[j];  // Очередная цифра

      if (M[k] != 0) {  // Цифра уже была
        retr = 1;
        break;
      } else
        M[k] = 1;  // Отметить, что была
    }

    if (retr)
      continue;  // Повторение цифр

    toDigit(B1, 2 * vv);  // Разложение СОСТАВ

    if (B1[0] != B1[2])
      continue;  // Нет двух букв С

    if (M[B1[0]])
      continue;  // цифра на месте С уже была в ВАГОН

    if (A1[3] != B1[1])
      continue;  // буква О должна быть в ВАГОН

    if (A1[0] != B1[5])
      continue;  // буква В должна быть в ВАГОН

    if (A1[1] != B1[4])
      continue;  // буква A должна быть в ВАГОН

    if (B1[0] == B1[3]  // цифры на месте С и Т - д.б. разные
        || M[B1[3]])  // цифра на месте Т уже была в ВАГОН
      continue;

    printf("%d+%d=%d\n", vv, vv, 2 * vv);
  }

  getchar();
}

7. Результаты работы

85679+85679=171358

Лабораторный практикум

1. Простые числа. Способ с вычеркиванием, не использующий деления. Генерируется массив натуральных чисел A[i]=i. Затем берется k=2 и вычеркиваются все кратные ему. Далее ищется следующее невычеркнутое и процесс вычеркивания кратных повторяется.

2. Замечательное число. Мегамозг придумал десятизначное натуральное число. Первая (слева) цифра этого числа равна количеству нулей в его записи, вторая цифра — количеству единиц, третья — количеству двоек и т.д., последняя цифра равна количеству девяток в записи этого числа. А вы сможете повторить достижение Мегамозга и найти это число?

3. Удвоение числа. Некоторое натуральное число заканчивается на двойку. Если ее переставить на первое место, то число удвоится. Какое минимальное число было изначально?

4. Замечательное число. Мегамозгу необходимо из 8 различных цифр составить число, делящееся на любую из этих цифр. Может ли Мегамозг придумать такое число? Если да, то какое число получилось?

5. Три разные цифры. Мегамозг выбрал три разные цифры и записал все возможные трехзначные натуральные числа, десятичная запись каждого из которых содержит все три выбранные цифры, но не может начинаться с нуля. Выяснилось, что сумма всех записанных чисел равна 3376. Найдите, какие цифры выбрал Мегамозг, и докажите, что других вариантов нет.

6. Прогулка по улице. Мегамозг живет и работает на одной улице. Из дома до работы он ходит пешком. Однажды он сосчитал сумму номеров домов, которые он проходил мимо (включая номер дома и номер здания, где работает). В сумме он получил 297. Назовите номера домов, в которых живет и работает Мегамозг, с учетом того, что между домом и работой Мегамозга не менее 8 домов (не включая дом и работу) и дома он считал только по одной стороне улицы. Расположение домов на улицах стандартное, в номерах домов нет индексов-букв.

7. Делимость чисел. Учитель написал на доске некое натуральное число. После этого первый ученик сказал: «Это число делится на 1». Второй сказал: «Это число делится на 2», ..., 50-й сказал: «Это число делится на 50». И что интересно, только двое из них были неправы. Более того, два неверных утверждения были сделаны подряд одно за другим. Какое наименьшее число мог написать на доске учитель?

8. Найти три положительных целых числа, сумма которых, а также сумма каждой пары которых есть точный квадрат.

9. При каких n число 10101...01 (чередующиеся n eдиниц, n–1 нулей) является простым?

10. Найти все натуральные числа, которые при умножении на 4 превращаются в свое зеркальное отражение. (Зеркальное отражение — это когда цифры в нем идут в обратном порядке).

11. Числовой ребус: СИНУС + СИНУС + КОСИНУС = ТАНГЕНС

12. Числовой ребус: Если АБВГ = ДДД, а ДВГ-АБ = ВВ, то чему равно произведение АБ*Г?

13. Числовой ребус: УХА * ХАУ = У00Х0А (0 это ноли)

14. Числовой ребус: ОХОХО + АХАХА = АХАХАХ

15. Числовой ребус: В этом примере на умножение присутствуют все цифры от 0 до 9, причем каждая цифра встречается только однажды (цифры в промежуточных выкладках в расчет не идут). Решите этот пример. Чтобы вам было от чего отправляться, мы вписали во второй сомножитель одну цифру.

    X X X 
      X 5
---------
X X X X X 

16. Числовой ребус: Найдите числа, зашифрованные словами КУБ и БУК, если известно, что число КУБ - действительно является кубом некоторого числа, а БУК - простое число.

17. Числовой ребус: ЛЮБА + ЛЮБИТ = АРБУЗЫ

18. Числовой ребус: ЛИРИК = 0,5*ФИЗИКА

19. Числовой ребус: ОДИН + ОДИН = МНОГО

20. Числовой ребус: НИТКА + НИТКА = ТКАНЬ

21. Числовой ребус: ПРИМЕР+РИМЕР+ИМЕР+МЕР+ЕР+Р=ЗАДАЧА

22. Числовой ребус: ДРАМА + ДРАМА = ТЕАТР

23. Числовой ребус КОШКА + КОШКА + КОШКА = СОБАКА

24. Умножение дат. В 1928 г. были четыре даты, обладающие замечательным свойством: при записи их обычным образом произведение числа на месяц дает год. Вот эти даты: 28/1 — 28, 14/2 — 28, 7/4 — 28 и 4/7 — 28. Сколько раз в нашем веке (с 1901 по 2000 г. включительно) встречается такое свойство? Может быть, вы попытаетесь найти год нашего столетия, в котором число таких дат максимально? Существует лишь один такой год.

25. Головоломка профессора Рэкбрейна. Какое число, будучи умноженным на 18, 27, 36, 45, 54, 63, 72, 81 или 99, дает произведение, у которого первая и последняя цифры совпадают с соответствующими цифрами множителя, а будучи умноженным на 90, дает произведение, у которого последние две цифры совпадают с цифрами множителей?

26. Квадраты-палиндромы. Вот любопытный предмет для исследований: найти квадраты целых чисел, которые можно читать как обычным образом, так и справа налево. Некоторые из них найти очень легко. Например, квадраты чисел 1, 11, 111 и 1111 равны соответственно 1, 121, 12321 и 1 234321.Все получившиеся числа — палиндромы, и данное правило применимо к любому числу единиц, не превосходящему 9. Однако существуют и другие случаи, которые мы могли бы назвать нерегулярными. Например, 2642 = 69 696, а 22852 = 5 221 225. Во всех приведенных выше примерах число цифр было нечетным. Не мог бы читатель привести примеры с четным числом цифр?

27. Два множителя. Найдите два целых числа, разность между которыми минимальна, а их произведение равно 1 234 567 890.

28. Деление на 11. Если девять цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 записаны в случайном порядке, например 412 539 768, то какова вероятность того, что получившееся число делится на 11? То число, которое я выписал, конечно, не делится на 11, но если в нем поменять местами 1 и 8, то оно будет делиться на 11. (Вместо вероятности – количество чисел)

29. Задача о десяти цифрах. Расставьте все десять цифр 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 в таком порядке, чтобы получившееся число делилось на все числа от 2 до 18. Если, например, разместить цифры в последовательности 1 274 953 680, то получившееся число будет делиться на 2, 3, 4, 5 и т. д. до 16, но не разделится на 17.

30. Тройки и семерки. Какое наименьшее число обладает тем свойством, что оно записывается только с помощью цифр 3 и 7 и что как оно, так и сумма его цифр делятся на 3 и 7? Например, 7 733 733 делится без остатка на 3 и на 7, но сумма его цифр (33) на 3 делится, а на 7 нет, поэтому оно не может служить решением задачи.

31. Три различные цифры. Профессор предложил студентам найти все числа, составленные из трех различных цифр, каждое из которых делится на квадрат суммы своих цифр. Так, в случае числа 112 сумма цифр равна 4, квадрат ее равен 16 и 112 делится на 16, но, к несчастью, 112 составлено не из трех различных цифр.

32. Цифры и кубы. Профессор Рэкбрейн попросил недавно своих молодых друзей найти все пятизначные квадраты, у которых сумма чисел, образованных двумя первыми и двумя последними цифрами, равна точному кубу. Так, если мы возьмем квадрат числа 141, равный 19 881, и прибавим 81 к 19, то получим 100 — число, не являющееся, к сожалению, точным кубом.

33. Цифры и квадраты. Одна из небольших рождественских головоломок профессора Рэкбрейна гласит следующее: чему равны наименьший и наибольший квадраты, содержащие все десять цифр от 0 до 9, причем каждую цифру — лишь по одному разу?

34. Цифровые квадраты. Найти число, которое вместе со своим квадратом содержало бы по одному и только одному разу каждую из девяти цифр, исключая нуль. Так, если бы квадрат числа 378 равнялся 152 694, то это число нам бы подошло. Но на самом деле его квадрат равен 142 884, что дает нам две четверки и три восьмерки, а 6, 5 и 9 отсутствуют.

35. Девять цифр. Если 32 547 891 умножить на 6, использовав каждую из девяти цифр один и только один раз, то получится произведение, равное 195 287 346 (также содержащее девять цифр по одному и только одному разу). Не могли бы вы найти другое число, обладающее тем же свойством при умножении на 6? Помните, что каждая из девяти цифр должна появиться один и только один раз как в сомножителях, так и в произведении.

36. Интересный сомножитель. Какое число обладает тем свойством, что если его умножить на 1, 2, 3, 4, 5 или 6, то в ответе появятся лишь те цифры, которые содержатся в записи исходного числа?

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

38. Найти число, при делении на которое три числа 480 608, 508 811 и 723 217 давали бы один и тот же остаток.

39. Перестановка цифр. Если мы хотим умножить 571 428 на 5 и разделить на 4, то для этого нам нужно лишь переставить 5 из начала в конец: число 714 285 дает верный ответ. Не сумели бы вы найти число, которое можно было бы умножить на 4 и разделить затем на 5 столь же просто: переставив первую цифру в конец?

40. Два куба. «Не могли бы вы найти,— спросил профессор Рэкбрейн,— два последовательных куба, разность между которыми была бы полным квадратом? Например, З3 = 27, а 23 = 8, но их разность (19) не является полным квадратом». Каково наименьшее возможное решение?

41. Составные квадраты. Можете ли вы найти два трехзначных квадрата (без нулей), которые, будучи выписанными подряд, образуют шестизначное число, в свою очередь представляющее собой квадрат? Например, из 324 и 900 (182 и 302) получается 324 900 (5702), но число 900 содержит два нуля, что запрещено условием. Задача имеет лишь одно решение.

42. Квадраты в арифметической прогрессии. Как-то утром профессор Рэкбрейн предложил своим молодым друзьям найти три целых числа, образующих арифметическую прогрессию, при этом сумма любых двух из этих трех чисел должна представлять собой квадрат.

43. Дополнение до квадрата. «Какое число,— спросил полковник Крэкхэм,— обладает тем свойством, что если его прибавить к числам 100 и 164 в отдельности, то каждый раз получатся точные квадраты?»

44. Арифметика в такси. Водитель такси не отличался вежливостью, и возмущенный мистер Уилкинс попросил его назвать свой номер. — Вы хотите узнать мой номер? — сказал водитель.— Что же, пожалуйста. Если вы разделите его на 2, 3, 4, 5 или 6, то получите в остатке 1, а на 11 он разделится без остатка. Скажу еще, что из всех водителей, которые могли бы сказать о своем номере то же самое, мой номер самый маленький. Какой номер был у водителя?

45. Геометрическая прогрессия. Профессор Рэкбрейн предложил однажды утром своим друзьям найти не менее трех целых чисел, которые образуют геометрическую прогрессию, начинающуюся с 1, и сумма которых должна быть точным квадратом. Например, 1+2 + 4 + 8 + 16 +32 = 63. Однако последнему числу, чтобы стать квадратом, не хватает единицы.

Лабораторный практикум (старый вариант)

Арифметические задачи

1. Любая целочисленная денежная сумма n> 7 может быть выдана без сдачи “трешками” и “пятерками”. Программа находит эти числа для заданного n.

2. Задумано целое число. Известны k,m,n остатки от деления числа на 3,5,7. Найти это число.

3. На заданном интервале найти все числа, цифры которых находятся в строго возрастающем порядке (например, 532).

4. Число Армстронга такое число из k цифр, для которого сумма k-х степеней его цифр равна самому этому числу, например 153=1 3 +5 3 +3 3 . Найти все трехзначные числа Армстронга.

5. Найти все двухзначные (трехзначные) числа, которые совпадают с последними цифрами своих квадратов, например, 25 2 =625, 76 2 =5676.

6. Число делится на 11, если разность между суммой цифр на четных и нечетных местах делится на 11. Проверить это факт для всех чисел заданного диапазона.

7. Число называется совершенным, если оно равно сумме всех своих делителей, например, 6=1+2+3, 28=1+2+4+7+14. Найти все совершенные числа в заданном интервале.

8. Найти все числа в заданном диапазоне, которые делятся на любую из своих цифр.

9. Составить алгоритм решения ребуса РАДАР=(Р+А+Д)^4 (различные буквы означают различные цифры, старшая - не 0).

10. Составить алгоритм решения ребуса МУХА+МУХА+МУХА=СЛОН (различные буквы означают различные цифры, старшая - не 0).

11. Составить алгоритм решения ребуса ДРУГ-ГУРД=2727 (различные буквы означают различные цифры, старшая - не 0).

12. Известно, что 1 января 1999 г. – пятница. Для любой заданной даты программа должна выводить день недели.

13. Известно, что 1 января 1999 г. – пятница. Программа должна найти все «черные вторники» и «черные пятницы» 1999 года (то есть – 13 числа).

Арифметические задачи на массивах

1. Найти в массиве и вывести значение наиболее часто встречающегося элемента.

2. Найти в массиве элемент, наиболее близкий к среднему арифметическому суммы его элементов.

3. Найти наименьшее общее кратное всех элементов массива (то есть числа, которое делится на все элементы).

4. Найти наибольший общий делитель всех элементов массива (на который они все делятся без остатка).

5. Интервал между минимальным и максимальным значениями элементов массива разбить пополам и относительно этого значения разделить массив на две части – меньшие слева, большие справа (части не сортировать).

6. Задан массив, определить значение k, делящее массив на две части так, чтобы разность сумм (по модулю) справа и слева была минимальна («центр тяжести» массива).

7. Найти в массиве наибольшее число подряд идущих одинаковых элементов (например {1,5,3,6,6,6,6,6,3,4,4,5,5,5} = 5).

8. Найти в массиве все пары одинаковых, рядом стоящих элементов и удалить.

9. Удалить из массива все отрицательные элементы.

10. Найти в массиве все пары взаимно простых элементов (не обязательно рядом стоящих) и вывести.

11. Найти в массиве все последовательности возрастающих элементов и копировать в выходной массив.

12. Удалить из массива все не простые числа (оставить простые)

13. Найти в массиве все пары элементов (не обязательно рядом стоящих), у которых последняя цифра первого элемента равна первой цифре второго и вывести.

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

15. Определить количество неповторяющихся значений элементов массива (например 1,7,2,8,1,1,1,2,5,7,7 -> 2).

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

17. Выделить в массиве возрастающую последовательность, начиная с первого элемента и перенести ее в другой массив (например, 3 ,2,1, 4 , 6 ,3, 8 ,1,1, 12 -> 3,4,6,8,12).

Вопросы без ответов

Содержательно сформулировать результат выполнения функции, определить «смысл» отдельных переменных, найти стандартные контексты, их определяющие, написать вызов функции.

Пример выполнения тестового задания.

//------------------------------------------------------42-05.cpp
//--------------------------------------------------------
int test(int a) {
  int n, k, i;

  for (n = a; n != 0; n /= 10) {
    k = n % 10;

    if (k == 0)
      break;  // Цифра - 0

    if (k == 1)
      continue;  // Цифра - 1

    for (i = 2; i < k; i++)

      if (k % i == 0)
        break;  // Цифра не простая

    if (k != i)
      break;  // Цифра не простая
  }

  if (n == 0)
    return 1;  // Дошли до конца без break -

  return 0;
}  // все цифры простые.

#include <stdio.h>

void main() {
  printf("test(1357)=%d\n", test(1357));
  printf("test(1457)=%d\n", test(1457));
}

Функция возвращает логическое значение, то есть производит проверку свойств числа a. Внешний цикл выделяет в нем последовательность цифр, очередная цифра хранится в переменной k. Внутренний цикл проверяет свойства делимости этой цифры. Причем как после внешнего, так и после внутреннего цикла проверяется условие «естественного» выхода из цикла: похоже, проверяются свойства всеобщности или существования. Внутренний цикл, проверяющий на цифру k на делимость в диапазоне от 2 до k-1, определяет, является ли k простым. Тогда оба цикла проверяют один из 3 возможных вариантов: все цифры числа – простые, все цифры числа – не простые, в числе есть те и другие цифры.

Для точной подгонки результата нужно проследить цепочку операторов break и условий, по которым они происходят. Самый внутренний break происходит при обнаружении делителя цифры (k – не простое). Следующий break происходит, если условие «естественного» выхода не было достигнуто, то есть был предыдущий break и выход из внешнего цикла происходит по тому же условию (k – не простое). Но последнее условие (n==0) является условием «естественного» завершения этого же цикла, то есть проверяется отсутствие предыдущего break по не простой цифре. Таким образом, функция проверяет, все ли цифры числа являются простыми. Поскольку цифры 0,1 внутренним циклом не проверяются, для них сделано исключение.

//------------------------------------------------------42-06.cpp
//--------------------------------------------------------1
int F1(int n) {
  for (int i = 2; n % i != 0; i++);

  return i;
}

//--------------------------------------------------------2
int F2(int n1, int n2) {
  for (int i = n1 - 1; !(n1 % i == 0 && n2 % i == 0); i--);

  return i;
}

//--------------------------------------------------------3
int F3(int n1, int n2) {
  int i = n1;
  if (i < n2)
    i = n2;

  for (; !(i % n1 == 0 && i % n2 == 0); i++);

  return i;
}

//--------------------------------------------------------4
int F4(int a) {
  for (int n = 2; n < a; n++) {
    if (a % n == 0)
      break;
  }

  if (n == a)
    return 1;

  return 0;
}

//--------------------------------------------------------5
int F5(int a) {
  for (int s = 0, n = 2; n < a; n++) {
    if (a % n == 0)
      s++;
  }

  if (s == 0)
    return 1;

  return 0;
}

//--------------------------------------------------------6
int F6(int a, int b) {
  for (int n = a; n % a != 0 || n % b != 0; n++);

  return n;
}

//--------------------------------------------------------7
int F7(int a, int b) {
  for (int n = a - 1; a % n != 0 || b % n != 0; n--);

  return n;
}

//--------------------------------------------------------8
int F8(int a) {
  int n, k, s;

  for (n = a, s = 0; n != 0; n = n / 10) {
    k = n % 10;
    s = s + k;
  }

  return s;
}

//--------------------------------------------------------9
int F9(int a) {
  int n, k, s;

  for (n = a, s = 0; n != 0; n = n / 10) {
    k = n % 10;
    if (k > s)
      s = k;
  }

  return s;
}

//--------------------------------------------------------10

int F10(int a) {
  int n, k, s;

  for (n = a, s = 0; n != 0; n = n / 10) {
    k = n % 10;
    s = s * 10 + k;
  }

  return s;
}

//--------------------------------------------------------11
void F11() {
  int a, n, k, s;

  for (a = 10; a < 30000; a++) {
    for (n = a, s = 0; n != 0; n = n / 10) {
      k = n % 10;
      s = s + k;
    }

    if (a == s * s * s)
      printf("%d\n", a);
  }
}

//--------------------------------------------------------12

void F12(int a, int A[10]) {
  int i, n;

  for (i = 0, n = a; n != 0; i++, n = n / 10);

  for (A[i--] = -1, n = a; n != 0; i--, n = n / 10)
    A[i] = n % 10;
}

//-------------------------------------------------------13
void F13(int v, int A[], int m) {
  int i, n, a;

  for (i = 0, a = 2; a < v && i < m - 1; a++) {
    for (n = 2; n < a; n++) {
      if (a % n == 0)
        break;
    }

    if (n == a)
      A[i++] = a;
  }

  A[i] = 0;
}

//--------------------------------------------------------14
void F14(int v, int A[], int m) {
  int i, n, a, j;

  for (i = 0, a = 2; a < v && i < m - 1; a++) {
    for (j = 0; j < i; j++) {
      if (a % A[j] == 0)
        break;
    }

    if (j == i)
      A[i++] = a;
  }

  A[i] = 0;
}

//--------------------------------------------------------15
void F15(int val, int A[], int n) {
  int m, i;

  for (i = 0; i < n - 1 && val != 1; i++) {
    for (m = 2; val % m != 0; m++);

    val /= m;
    A[i] = m;
  }

  A[i] = 0;
}

//--------------------------------------------------------16
int F16(int c[], int n) {
  int i, j;

  for (i = 0; i < n - 1; i++)
    for (j = i + 1; j < n; j++)
      if (c[i] == c[j])
        return i;

  return -1;
}

//--------------------------------------------------------17
int F17(int n) {
  int k, m;

  for (k = 0, m = 1; m <= n; k++, m = m * 2);

  return k - 1;
}

//--------------------------------------------------------18
void F18(int c[], int n) {
  int i, j, k;

  for (i = 0, j = n - 1; i < j; i++, j--) {
    k = c[i];
    c[i] = c[j];
    c[j] = k;
  }
}

//--------------------------------------------------------19
int F19(int c[], int n) {
  int i, j, k1, k2;

  for (i = 0; i < n; i++) {
    for (j = k1 = k2 = 0; j < n; j++)
      if (c[i] != c[j]) {
        if (c[i] < c[j])
          k1++;
        else
          k2++;
      }

    if (k1 == k2)
      return i;
  }

  return -1;
}

//--------------------------------------------------------20
int F20(int c[], int n) {
  int i, j, m, s;

  for (s = 0, i = 0; i < n - 1; i++) {
    for (j = i + 1, m = 0; j < n; j++)
      if (c[i] == c[j])
        m++;

    if (m > s)
      s = m;
  }

  return s;
}

//--------------------------------------------------------21
int F21(int c[], int n) {
  int i, j, k, m;

  for (i = k = m = 0; i < n - 1; i++)
    if (c[i] < c[i + 1])
      k++;

    else {
      if (k > m)
        m = k;

      k = 0;
    }

  return m;
}