Online-knigi.org
online-knigi.org » Книги » Компьютеры и интернет » Базы данных » Рассказы о математике с примерами на языках Python и C (СИ) - Елисеев Дмитрий Сергеевич (читать книги онлайн полные версии txt) 📗

Рассказы о математике с примерами на языках Python и C (СИ) - Елисеев Дмитрий Сергеевич (читать книги онлайн полные версии txt) 📗

Тут можно читать бесплатно Рассказы о математике с примерами на языках Python и C (СИ) - Елисеев Дмитрий Сергеевич (читать книги онлайн полные версии txt) 📗. Жанр: Базы данных / Математика. Так же Вы можете читать полную версию (весь текст) онлайн без регистрации и SMS на сайте online-knigi.org (Online knigi) или прочесть краткое содержание, предисловие (аннотацию), описание и ознакомиться с отзывами (комментариями) о произведении.
Перейти на страницу:

Во-первых, слегка оптимизируем приведенную выше программу. Как нетрудно видеть, если число N делится нацело на P, то мы «автоматом» сразу находим и второй делитель N/P. Например, если 10 делится нацело на 2, то оно делится и на 10 / 2 = 5. Это позволяет заметно сократить число вариантов перебора. Во-вторых, используем тип чисел Decimal, позволяющий использовать большие числа. Обновленная программа выглядит так:

from decimal import *

def is_perfect(n):

    s = Decimal(1)

    p = Decimal(2)

    while p < n.sqrt()+1:

        if n % p == 0:

            s += p

            if p != n/p: s += n/p

        p += 1

    return s == n

print(is_perfect(Decimal('137438691328')))

Запускаем, программа работает — число '137438691328' действительно является совершенным. Оно делится на 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524287, 1048574, 2097148, 4194296, 8388592, 16777184, 33554368, 67108736, 134217472, 268434944, 536869888, 1073739776, 2147479552, 4294959104, 8589918208, 17179836416, 34359672832 и 68719345664, сумма этих чисел равна 137438691328. Однако, на моем компьютере проверка «совершенности» данного числа заняла… 54 секунды. Это конечно быстро по сравнению с 16-м веком, но совершенно недостаточно чтобы проверить все числа, хотя бы до миллиарда. Значит пора использовать более тяжелую артиллерию — перепишем программу на языке Си. Все-таки Python это интерпретатор, и работает заметно медленнее. Получаемый код не намного сложнее:

#include <string.h>

#include <math.h>

#include <stdbool.h>

#include <stdint.h>

bool isPerfect(unsigned long long int n)

{

  unsigned long long int sum = 1, i;

  for(i=2; i<=sqrt(n)+1; i++)

  {

    if (n%i==0) {

      sum += i;

      if (i != n/i) {

        sum += n/i;

      }

    }

  }

  return sum == n;

}

int main()

{

  unsigned long long int n = 137438691328LL;

  bool res = isPerfect(n);

  printf("%dn", res);

  return 0;

}

Компилируем программу с помощью компилятора gcc, запускаем получившийся exe-файл: время выполнения меньше секунды, уже гораздо лучше. Теперь несложно поменять функцию main для перебора всех чисел от 1 до 200000000000. В код также добавлен вывод промежуточных результатов каждые 1000000 итераций, чтобы видеть ход выполнения программы.

int main()

{

  unsigned long long int MAX = 200000000000LL;

  unsigned long long int p;

  for (p=1; p<MAX; p++) {

    if (isPerfect(p))

      printf(" %llu ", p);

        if (p % 1000000 == 0)

          printf("*%llu,%llu*", 100*p/MAX, p);

  }

}

Увы, прогноз относительно скорости расчетов оказался слишком оптимистичным. Примерно за час работы программы, было перебрано лишь 100 млн. вариантов, а для перебора всех 200 млрд. понадобился бы не один день. Желающие могут продолжить процесс самостоятельно, однако с уверенностью можно сказать что в диапазоне от 1 до 100000000 действительно нет совершенных чисел кроме 6, 28, 496, 8128 и 33550336.

Проверка числа 2 305 843 008 139 952 128 является непростой задачей даже для современного домашнего компьютера — во-первых, в языке C/C++ нет встроенных типов данных для столь большого числа, а во-вторых, число вариантов перебора весьма велико.

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

7. Магический квадрат

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

Рассказы о математике с примерами на языках Python и C (СИ) - img_14.jpeg

Магический квадрат 4х4 был обнаружен в индийских надписях 11 века:

Рассказы о математике с примерами на языках Python и C (СИ) - img_15.jpeg

И наконец, известный квадрат 4х4, изображенный на гравюре немецкого художника Дюрера «Меланхолия». Этот квадрат изображен не просто так, 2 числа 1514 указывают на дату создания гравюры.

Рассказы о математике с примерами на языках Python и C (СИ) - img_16.jpeg

Как можно видеть, уже математики прошлого умели строить магические квадраты разной размерности. Интересно рассмотреть их свойства.

Сумма чисел магического квадрата размера NxN зависит только от N, и определяется формулой:

Рассказы о математике с примерами на языках Python и C (СИ) - img_17.jpeg

Это несложно доказать, т. к. сумма всех чисел квадрата равна сумме ряда 1..N2. Действительно, для квадрата Дюрера M(4) = 34, что можно посчитать на картине. Для квадратов разной размерности суммы равны соответственно: M(3) = 15, M(4) = 34, M(5) = 65, M(6) = 111, M(7) = 175, M(8) = 260, M(9) = 369, M(10) = 505.

Перейти на страницу:

Елисеев Дмитрий Сергеевич читать все книги автора по порядку

Елисеев Дмитрий Сергеевич - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки mir-knigi.info.


Рассказы о математике с примерами на языках Python и C (СИ) отзывы

Отзывы читателей о книге Рассказы о математике с примерами на языках Python и C (СИ), автор: Елисеев Дмитрий Сергеевич. Читайте комментарии и мнения людей о произведении.


Уважаемые читатели и просто посетители нашей библиотеки! Просим Вас придерживаться определенных правил при комментировании литературных произведений.

  • 1. Просьба отказаться от дискриминационных высказываний. Мы защищаем право наших читателей свободно выражать свою точку зрения. Вместе с тем мы не терпим агрессии. На сайте запрещено оставлять комментарий, который содержит унизительные высказывания или призывы к насилию по отношению к отдельным лицам или группам людей на основании их расы, этнического происхождения, вероисповедания, недееспособности, пола, возраста, статуса ветерана, касты или сексуальной ориентации.
  • 2. Просьба отказаться от оскорблений, угроз и запугиваний.
  • 3. Просьба отказаться от нецензурной лексики.
  • 4. Просьба вести себя максимально корректно как по отношению к авторам, так и по отношению к другим читателям и их комментариям.

Надеемся на Ваше понимание и благоразумие. С уважением, администратор online-knigi.org


Прокомментировать
Подтвердите что вы не робот:*