Для тренировки решения алгоритмов, а это база любого программиста, есть отличный ресурс: проект Эйлера, с задачами, уровень сложности которых усложняется по мере их возрастания. Всего задач в проекте более 700-та, напротив каждой показано количество пользователей ее решивших.
Если решить самостоятельно 50 первых задач или хотя бы проанализировать и понять как они выполняются, можно сказать, что вы достигли хорошего уровня в программировании алгоритмов.
В данной статье будут решены и проанализированы первые 10-ть задач.
1. Multiples of 3 and 5 / Числа, кратные 3 или 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел равна 23.
Найдите сумму всех чисел меньше 1000, кратных 3 или 5.
Решение:
function task1($num) {
$sum = 0;
for ($i = 0; $i < $num; $i++){
if ($i % 3 == 0 || $i % 5 == 0) {
$sum = $sum + $i;
}
}
return $sum;
}
$res1 = task1(1000);
echo $res1; // 233168
2. Even Fibonacci numbers / Четные числа Фибоначчи
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Каждый следующий элемент ряда Фибоначчи получается при сложении двух предыдущих. Начиная с 1 и 2, первые 10 элементов будут: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Найдите сумму всех четных элементов ряда Фибоначчи, которые не превышают четыре миллиона.
Решение:
function task2($limit){
$sum = 0;
$a = 0;
$b = 1;
while ($b < $limit){
if ($b % 2 == 0) {
$sum = $sum + $b;
}
$h = $a + $b;
$a = $b;
$b = $h;
}
return $sum;
}
$res2 = task2(4000000);
echo $res2; // 4613732
3. Largest prime factor / Наибольший простой делитель
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Простые делители числа 13195 — это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?
Решение:
set_time_limit(300);
function isPrime($n) {
for($i = 2; $i <= sqrt($n); $i++) {
if($n % $i == 0) {
return false;
}
}
return true;
}
function task3($limit) {
$max = 0;
for ($i = 1; $i < $limit; $i++) {
if (isPrime($i) && $limit % $i == 0) {
$max = $i;
}
}
return $max;
}
$res3 = task3(600851475143);
echo $res3; // 6857
Вышеуказанное решение правильное, но с большими числами оно не будет работать. Для этого есть решение №2:
function task3($n)
{
$i = 2;
while ($i * $i < $n) {
while ($n % $i == 0) {
$n = $n / $i;
}
$i = $i + 1;
}
return $n;
}
$res3 = task3(600851475143);
echo $res3; // 6857
4. Largest palindrome product / Наибольшее произведение-палиндром
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
Число-палиндром с обеих сторон (справа налево и слева направо) читается одинаково. Самое большое число-палиндром, полученное умножением двух двузначных чисел – 9009 = 91 × 99.
Найдите самый большой палиндром, полученный умножением двух трехзначных чисел.
Решение:
function isPalindrome($palindrom) {
$palindrom = strval($palindrom);
$pal = strlen($palindrom) - 1;
for ($i = 0; $i < $pal; $i++) {
if ($palindrom[$i] !== $palindrom[$pal - $i]) {
return false;
}
}
return true;
}
function largestPalindrome(){
$largestPalindrome = 0;
for ($a = 100; $a <= 999; $a++) {
for ($b = 100; $b <= 999; $b++) {
if (isPalindrome($a * $b) and $a * $b > $largestPalindrome) {
$largestPalindrome = $a * $b;
}
}
}
return $largestPalindrome;
}
$res4 = largestPalindrome();
echo $res4; // 906609
5. Smallest multiple / Наименьшее кратное
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
2520 — самое маленькое число, которое делится без остатка на все числа от 1 до 10.
Какое самое маленькое число делится нацело на все числа от 1 до 20?
Решение:
function isDevisible($number) {
for ($i = 2; $i < 21; $i++) {
if ($number % $i != 0) {
return 'false';
}
}
return 'true';
}
$number = 20;
while (true) {
if (isDevisible($number)) {
break;
} else {
$number = $number + 20;
}
}
echo $number; // 232792560
6. Sum square difference / Разность между суммой квадратов и квадратом суммы
The sum of the squares of the first ten natural numbers is,12+22+…+102=385
The square of the sum of the first ten natural numbers is,(1+2+…+10)2=552=3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025−385=2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Сумма квадратов первых десяти натуральных чисел равна 12 + 22 + … + 102 = 385
Квадрат суммы первых десяти натуральных чисел равен(1 + 2 + … + 10)2 = 552 = 3025
Следовательно, разность между суммой квадратов и квадратом суммы первых десяти натуральных чисел составляет 3025 − 385 = 2640.
Найдите разность между суммой квадратов и квадратом суммы первых ста натуральных чисел.
Решение:
function difNatural(){
$sum_kv = 0;
for ($i = 1; $i < 101; $i++) {
$sum = $i * $i;
$sum_kv = $sum_kv + $sum;
}
$sum1 = 0;
for ($j = 1; $j < 101; $j++) {
$sum1 = $sum1 + $j;
}
$sum_kv1 = pow($sum1, 2);
return ($sum_kv1 - $sum_kv);
}
$res6 = difNatural();
echo $res6;//25164150
7. 10001st prime / 10001-ое простое число
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-ое простое число — 13.
Какое число является 10001-ым простым числом?
Решение:
function isPrime($n) {
for($i = 2; $i <= sqrt($n); $i++) {
if($n % $i == 0) {
return false;
break;
}
}
return true;
}
function nthPrime($n){
$count = 0;
$inc = 2;
while ($count < $n) {
if (isPrime($inc)) {
$count++;
echo "</br>";
}
$inc++;
}
return $inc - 1;
}
$res7 = nthPrime(10);
echo $res7; // 104743
8. Largest product in a series / Наибольшее произведение в последовательности
The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
Наибольшее произведение четырех последовательных цифр в нижеприведенном 1000-значном числе равно 9 × 9 × 8 × 9 = 5832.
731671765313 … 2963450
Найдите наибольшее произведение тринадцати последовательных цифр в данном числе.
Решение:
$num = '731671765313306249192 .... 2963450';
function max_mul($num){
$p = strval($num);
$pa = strlen($num) - 12;
$st = 0;
$n = 13;
for ($i = 0; $i < $pa; $i++){
$sum = 1;
for ($j = 0; $j < $n; $j++) {
$sum = $sum * $p[$i + $j];
}
if ($sum > $st) {
$st = $sum;
}
}
return $st;
}
$res8 = max_mul($num);
echo $res8;// 23514624000
9. Special Pythagorean triplet / Особая тройка Пифагора
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
Тройка Пифагора — три натуральных числа a < b < c, для которых выполняется равенствоa2 + b2 = c2
Например, 32 + 42 = 9 + 16 = 25 = 52.
Существует только одна тройка Пифагора, для которой a + b + c = 1000.
Найдите произведение abc.
Решение:
function numPifagor()
{
for ($a = 1; $a < 1000; $a++) {
for ($b = 1; $b < $a; $b++) {
$c = 1000 - $a - $b;
if (((pow($a, 2)) + (pow($b, 2)) === (pow($c, 2))) &&
($a + $b + $c === 1000)) {
return $a * $b * $c;
}
}
}
}
$res9 = numPifagor();
echo $res9 ; //31875000
10. Summation of primes / Сложение простых чисел
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17.
Найдите сумму всех простых чисел меньше двух миллионов.
Решение:
set_time_limit(300);
function isPrime($n) {
for($i = 2; $i <= sqrt($n); $i++) {
if($n % $i == 0) {
return false;
break;
}
}
return true;
}
function nthPrime($n){
$inc = 2;
$sum = 0;
while ($inc < $n) {
if (isPrime($inc)) {
$sum = $inc + $sum;
}
$inc++;
}
return $sum;
}
$res7 = nthPrime(2000000);
echo $res7; //142913828922