Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
 iakovlev.org 
 Languages
 С
 GNU С Library 
 Qt 
 STL 
 Threads 
 C++ 
 Samples 
 stanford.edu 
 ANSI C
 Libs
 LD
 Socket
 Pusher
 Pipes
 Encryption
 Plugin
 Inter-Process
 Errors
 Deep C Secrets
 C + UNIX
 Linked Lists / Trees
 Asm
 Perl
 Python
 Shell
 Erlang
 Go
 Rust
 Алгоритмы
NEWS
Последние статьи :
  Тренажёр 16.01   
  Эльбрус 05.12   
  Алгоритмы 12.04   
  Rust 07.11   
  Go 25.12   
  EXT4 10.11   
  FS benchmark 15.09   
  Сетунь 23.07   
  Trees 25.06   
  Apache 03.02   
 
TOP 20
 MINIX...3057 
 Solaris...2933 
 LD...2904 
 Linux Kernel 2.6...2470 
 William Gropp...2181 
 Rodriguez 6...2012 
 C++ Templates 3...1945 
 Trees...1937 
 Kamran Husain...1866 
 Secure Programming for Li...1792 
 Максвелл 5...1710 
 DevFS...1694 
 Part 3...1684 
 Stein-MacEachern-> Час...1632 
 Go Web ...1624 
 Ethreal 4...1618 
 Arrays...1607 
 Стивенс 9...1603 
 Максвелл 1...1592 
 FAQ...1538 
 
  01.01.2024 : 3621733 посещений 

iakovlev.org

Алгоритмы - Проект Эйлера

Проект Эйлера — это набор задач по математике и программированию.
Проект был основан в октябре 2001.
Целевая аудитория проекта включает в себя студентов, которым мало университетского курса, не-математиков, которым, тем не менее, интересна математика, а также профессионалов, которым хотят быть в хорошей математической форме. Задачи эти разной степени сложности.
Каждая задача подчиняется "правилу одной минуты", которое гласит: несмотря на то, что на построение алгоритма решения могут уйти часы, эффективная реализация позволяет получить ответ на компьютере средней вычислительной мощности меньше, чем за одну минуту.

Здесь будут приведены реализации на трех языках - питоне, гоу и си. Питон - интерпретируемый язык, остальные - компиляторы. Я не буду сравнивать производительность реализаций в разрезе языков, потому что нет смысла сравнивать производительность интерпретатора и компилятора. Скорость работы программ зависит также и от других факторов, в частности от алгоритмов, заложенных в конкретную реализацию. Главное условие - любая программа должна уложиться в минуту.

Начнем с задачи №5.
2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10. Какое самое маленькое число делится нацело на все числа от 1 до 20?
В данной задаче можно использовать алгоритм Евклида для нахождения наибольшего общего делителя (НОД). В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.
Нахождение наименьшего общего кратного (НОК) по сути есть завуалированный вызов алгоритма Евклида.
Формируется цикл от 1 до 20, в котором вызывается функция lcm - наименьшего общего кратного.
Стек вызовов такой:
 1 1
 2 2
 6 3
 12 4
 60 5
 60 6
 420 7
 840 8
 2520 9
 2520 10
 27720 11
 27720 12
 360360 13
 360360 14
 360360 15
 720720 16
 12252240 17
 12252240 18
 232792560 19
 232792560 20
 232792560
 
Первое число в каждой строке является наименьшим общим кратным для всех чисел от единицы до текущего значения счетчика. Видно, что каждое такое число либо равно предыдущему, либо есть его произведению на другое целое число.

Python:
 
 def gcd(x, y):
     return x if y == 0 else gcd(y, x % y)
 
 def lcm(x, y):
     return (x * y) // gcd(x, y)
 
 g = 1
 for i in range(1, n + 1):
     g = lcm(g, i)
 print g, i
 
 
Go :
 
 package main
 
 import "fmt"
 
 func main() {
     p, t, lcd := 1, [2]int{}, 1
     for c:= 2; c <= 20; c++ {
         t[0], t[1], lcd = p, c, 1
         L: for {
             if t[0] > t[1] {
                 t[0] =  t[0] % t[1]
             } else { t[1] = t[1] % t[0] }
 
             if t[0] == 1 || t[1] == 1 { break L }
             if t[0] * t[1] == 0 {
                 if t[0] == 0 {
                     lcd = t[1]
                 } else { lcd = t[0] }
                 break L
             }
         }
         p *= c / lcd
     }
     fmt.Println(p)
 }
 
 
C:
 
 #include <stdio.h>
 
 unsigned long gcd(unsigned long a, unsigned long b) {
     unsigned long r;
     if (a > b) {
         unsigned long t = a;
         a = b;
         b = t;
     }
     while (r = a % b) {
         a = b;
         b = r;
     }
     return b;
 }
 
 unsigned long lcm(unsigned long a, unsigned long b) {
     unsigned long long p = (unsigned long long)a * b;
     return p / gcd(a, b);
 }
 
 int main(void) {
     unsigned long ans = 1;
     unsigned long i;
     for (i = 1; i <= 20; i++) {
         ans = lcm(ans, i);
     }
     printf("%lu\n", ans);
     return 0;
 }
 
 
Задача №9
Тройка Пифагора - три натуральных числа a < b < c, для которых выполняется равенство
a2 + b2 = c2
Например, 32 + 42 = 9 + 16 = 25 = 52.
Существует только одна тройка Пифагора, для которой a + b + c = 1000.
Найдите произведение abc.
Решение в лоб: вложенный цикл для a и b, внутри цикла складываем квадраты и проверяем условие равенства:

Python:
 
 for a in range(1, 501):                  
     for b in range(a, 501):              
         c = 1000 - a - b                 
         if a ** 2 + b ** 2 == c ** 2:    
             print(a,b,c, a * b * c)      
 
 
Go:
 
 package main
 
 import "fmt"
 
 const N = 50
 
 func main() {
     k, m, n := 1, N, N
     a, b, c, p := 0, 0, 0, 0
     L: for ; m > 1; m-- {
         n = m - 1
         for ; n > 1; n-- {
             k = 1
             for ; k < 30; k++ {
                 if 2 * k * m * (m + n) == 1000 {
                     a, b, c = k * (m * m - n * n), 2 * k * m * n, k * (m * m + n * n)
                     if a * b * c > 0 {
                         p = a * b * c
                         break L
                     }
                 }
             }
         }
     }
     fmt.Println(p)
 }
 
 
C:
 
 #include <   stdio.h>
 
 int main(void)
 {
   int a, b;
 
   for (a = 1; a <= 333; a++) {
     for (b = a; b <= 666; b++) {
       int c = (1000 - a - b);
       if (a*a + b*b == c*c) {
         printf("%d\n", a * b * c);
       }
     }
   }
   return 0;
 }
 
 
Задача №12
Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-ое треугольное число равно 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Перечислим делители первых семи треугольных чисел:
1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28
Как мы видим, 28 - первое треугольное число, у которого более пяти делителей.
Каково первое треугольное число, у которого более пятисот делителей?
Для решения используем формулу для суммы n подряд натуральных чисел:
sum = n*(n+1)/2

Python:
 
 def numDivisors(n):
     if n % 2 == 0:
         n = n/2
     divisors = 1
     count = 0
     while n % 2 == 0:
         count += 1
         n = n/2
     divisors = divisors * (count + 1)
     p = 3
     while n != 1:
         count = 0
         while n % p == 0:
             count += 1
             n = n/p
         divisors = divisors * (count + 1)
         p += 2
     return divisors
 def findTriangularIndex(factor_limit):
     n = 1
     lnum, rnum = numDivisors(n), numDivisors(n + 1)
     while lnum * rnum < 500:
         n += 1
         lnum, rnum = rnum, numDivisors(n + 1)
     return n
 index = findTriangularIndex(500)
 triangle = (index * (index + 1)) // 2
 print(triangle)
 
 
Go
 
 package main
 
 import "fmt"
 import "math"
 
 func main() {
     var n, m, c int
     for i := 1; ; i++ {
         n, m, c = i * (i + 1) / 2, int(math.Sqrt(float64(n))), 0
         for f := 1; f < m; f++ {
             if n % f == 0 { c++ }
         }
         c *= 2
         if m * m == n { c += 1 }
         if c > 500 {
             fmt.Println(n)
             break
         }
     }
 }
 
 
C:
 
 #include <stdio.h>
 
 static unsigned divisor_count(unsigned long n);
 
 int main(void)
 {
   unsigned long i = 1, n = 1;
 
   while (divisor_count(n) < 500) {
     n += ++i;
   }
   printf("%lu\n", n);
   return 0;
 }
 
 unsigned divisor_count(unsigned long n)
 {
   unsigned ret = 1;
   unsigned long i;
 
   for (i = 2; i <= n; i++) {
     unsigned c = 0;
     while (n % i == 0) {
       c++;
       n /= i;
     }
     ret *= c+1;
   }
   return ret;
 }
 
 
Еще одна математическая задача, которая не имеет отношения к проекту Эйлера.
Дано сколь угодно большое целое число.
Число можно рабить на части произвольным образом и между частями расставить знак плюс.
Для любого сколь угодно длинного числа можно свести его к однозначному (цифре) максимум за 4 иттерации.
Например - дано следующее число:
9845739457938475234237428374681231231545412354726877628981928491827549826435873244444444446826337468273463457373457345798798798534895
Его можно например разбить таким образом, что в сумме уже после первой итерации оно даст 10000790:
10000790 = 9 + 8 + 45 + 73 + 94 + 5 + 7 + 9 + 3 + 8 + 4 + 752 + 34 + 23 + 7 + 4 + 2 + 83 + 74 + 68 + 12 + 3 + 1 + 2 + 3 + 15 + 4 + 54 + 1 + 235 + 472 + 6 + 8 + 7 + 7 + 6 + 28 + 98 + 19 + 28491 + 8 + 2 + 75 + 49 + 8 + 26 + 4358 + 73244 + 4444 + 4 + 44 + 46 + 8 + 26 + 3 + 3 + 7 + 4 + 68 + 2 + 7346 + 3 + 4 + 5 + 73 + 73 + 4 + 5 + 7 + 3 + 4 + 57 + 9879879 + 8 + 5 + 3 + 4 + 89 + 5
 
 #!/usr/bin/env python3
 import os
 import sys
 from random import randrange
 
 t = '9845739457938475234237428374681231231545412354726877628981928491827549826435873244444444446826337468273463457373457345798798798534895'
 ll = len(t)
 print(t)
 cc = 0
 min = 0
 rr = [ 0 for i in range(1, ll+1)]
 while True:
     rr = [ 0 for i in range(1, ll+1)]
     c = 0
     while True:
         r = randrange(ll)
         rr[r] = 1 
         c += 1
         if c == ll:
             res = t[0]
             ress = []
             i = 1
             while True:
                 if i < ll:
                     if rr[i] == 0:    
                         res += t[i]
                     else:
                         ress.append(int(res))
                         res = t[i]
                     i += 1
                     if i == ll :
                         ress.append(int(t[len(t)-1]))
                         break
             sss = 0
             for ss in ress:
                 sss += ss
             s11 = str(sss)
             if s11[0] == '1':
                 f = 0
                 for s1 in s11:
                     if s1 == '0':
                         f += 1
                 if f > 4:
                     if len(s11)-f < 5:
                         summ = ''
                         for rrr in ress:
                             summ += str(rrr)
                         if summ == t:
                             #print(summ)
                             #print(t)    
                             print(s11, '=', ress)
                             exit(0)
                         
             break
 
 
 
 
 
 











Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье