Для поступления предлагалось пройти несколько этапов, решая логические/математические задачи.
Варианты решения некоторых типовых задач первого этапа я и попытаюсь разобрать в данной статье.
PS: Для удобства быстрого написания и отладки кода подсчетов использовался JavaScript.
Пока писал статью, смотрю, в песочнице меня уже опередили по теме. Однако, у меня рассмотрены другие типы задач, только одна совпала про степени (но, судя по комментариям, не в обиду автору — решение неверное).
Комментарии и предложения альтернативных вариантов решения только приветствуются.
Задача 1
Рассмотрим спираль, в которой, начиная с 1 в центре, последовательно расставим числа по часовой стрелке, пока не получится спираль 5 на 5:
Можно проверить, что сумма всех чисел на диагоналях равна 101.
Чему будет равна сумма чисел на диагоналях, для спирали размером 1195 на 1195?
Решение 1
Будем идти от самого центра по спирали и просто суммировать числа на углах: 1 + 3 + 5 + 7 + 9 + 13 + 17 + 21 + 25 +…
Можно заметить, что в этой последовательности каждое следующее число отличается на дельту d (вначале равную 2: 3, 5, 7, 9). При этом с каждым переходом на следующий виток спирали дельта между четырьмя угловыми числами увеличивается еще на 2: 13, 17, 21, 25.
Получается сумма значений угловых чисел одного витка рассчитывается по формуле: (v+d) + (v+2*d) + (v+3*d) + (v+4*d), где v — последнее число предыдущего витка (1, 9, 25, ...), d — дельта. Построим цикл, увеличивая дельту d до размера спирали size.
function task1(size) {
for (var v=1, d=2, sum=v; d<size; v+=4*d, d+=2) {
sum += 4*v+10*d;
}
return sum;
}
Альтернативное решение, как сумма квадратичной последовательности, предложенное eandr_67 в комментариях:
function task1_alt(size) {
return (size * size * size * 2 / 3.0 + size * size / 2.0 + size * 4 / 3.0 - 1.5);
}
Для спирали размером size = 1195 сумма чисел на диагоналях равна 1138375521.
Задача 2
Определим функцию P(n,k) следующим образом: P(n,k) = 1, если n может быть представлено в виде суммы k простых чисел (простые числа в записи могут повторяться, 1 не является простым числом) и P(n,k) = 0 в обратном случае.
К примеру, P(10,2) = 1, т.к. 10 может быть представлено в виде суммы 3 + 7 или 5 + 5, а P(11,2) = 0, так как никакие два простых числа не могут дать в сумме 11.
Определим функцию S(n) как сумму значений функции P(i,k) для всех i и k, таких что 1<=i<=n, 1<=k<=n.
Таким образом, S(2) = P(1,1) + P(2,1) + P(1,2) + P(2,2) = 1, S(10) = 20, S(1000) = 248838.
Найдите S(17688).
Решение 2
Воспользуемся свойствами простых чисел:
- Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел. (бинарная проблема Гольдбаха (или проблема Эйлера), на 2012 год проверена для всех чётных чисел, не превышающих 4?1018)
- Каждое нечётное число, большее 5, можно представить в виде суммы трёх простых чисел. (тернарная проблема Гольдбаха, доказана в 2013 году)
Для k>3 значения функции P(i,k) заполняются как следствия из предыдущих утверждений. При этом все четные числа i>=4 можно разложить максимум на k=i/2 простых чисел (k=i/2-1 для нечетных).
Составим наглядную матрицу, где i — числа от 1 до n, которые можно разложить на сумму k простых чисел:
Можно заметить, что существуют такие нечетные числа, которые не являются простыми, и при этом их нельзя представить как сумму двух простых чисел — в данном случае это, например, 27.
Ряд простых чисел можем подсчитать, проверяя каждое нечетное число на деление по модулю без остатка на все полученные ранее простые числа:
// функция определения простых чисел
function isPrime(x,primes){
for (var j=0, len=primes.length; j<len; j++){
if (x%primes[j]==0) return false;
}
return true;
}Итоговая функция подсчета S(n):
function task2(n) {
for (var i=4, count=2, primes=[2,3]; i<=n; i++){
// если число - четное
if (i%2==0) {
count+=i/2-1;
} else {
// нечетное
count+=(i-1)/2-1;
// если нельзя представить как сумму двух простых чисел
if (i!=(primes[primes.length-1]+2)) {
count--;
}
// если число - простое
if (isPrime(i,primes)) {
count++;
// добавляем новое простое число в общий ряд
primes[primes.length]=i;
}
}
}
return count;
}S(17688) = 78193870.
Задача 3
Число 125874 и результат умножения его на 2 — 251748 можно получить друг из друга перестановкой цифр. Найдите наименьшее положительное натуральное x такое, что числа 2*x, 3*x можно получить друг из друга перестановкой цифр.
Решение 3
Для простого сравнения чисел путем перестановки цифр будем приводить числа в строки с упорядоченными по возрастанию символами:
// получение строки упорядоченных символов
function sortVal(val) {
var str=val.toString();
if (str.length>1){
return str.split("").sort().join("");
} else {
return str;
}
}
И сравнивать эти строки с "упорядоченным" x.
В комментариях Large предложил исключить из перебора x, в которых первая цифра 4 и более: 412, 5230, 60457…, т.к. при перемножении увеличивается длина числа — и проверять такие x не имеет смысла.
Зададим такой максимум xFirstMax первой цифры x, как результат округленного целочисленного деления 9 и максимального из a и b.
function task3(a,b) {
// задаем предел первой цифры числа x для исключения таких x из перебора
var xFirstMax = Math.floor(9/Math.max(a,b));
for (var x=1, xSorted=''; x<=1000000; x++){
// пропускаем x, если его первая цифра больше предела
if (x.toString()[0]>xFirstMax) continue;
// сортируем цифры в текущем x
xSorted=sortVal(x);
// сравниваем с сортированными результатами перемножений x на a и b
if (xSorted==sortVal(a*x) && xSorted==sortVal(b*x)) {
var founded=x;
break;
}
}
return founded;
}Наименьшее положительное натуральное x = 142857 (где для a = 2 и b = 3: a*x = 285714 и b*x = 428571).
Задача 4
Если мы возьмем 47, перевернем его и сложим, получится 47 + 74 = 121 — число-палиндром.
Если взять 349 и проделать над ним эту операцию три раза, то тоже получится палиндром:
349 + 943 = 1292
1292 + 2921 = 4213
4213 + 3124 = 7337
Найдите количество положительных натуральных чисел меньших 13110 таких, что из них нельзя получить палиндром за 50 или менее применений описанной операции (операция должна быть применена хотя бы один раз).
Решение 4
50 операций прямого суммирования, может привести к очень большим числам, что, как подсказал в комментариях Stelet, закончится непредвиденными результатами. Поэтому будем хранить числа, как строки. А вместо множественных переворачиваний будем просто суммировать попарно цифры числа начиная с концов, что в итоге равнозначно сумме числа и его перевернутой копии.
И уже для проверки на палиндром достаточно перевернуть полученную строку и сравнить значение с самим собой: 7337==reverse(7337).
function task4(maxNum) {
for (var num=1, count=0; num<maxNum; num++){
// производим 50 операций суммирования с переворачиванием
for (var op = 1, val=num, palindrome=false; op<=50; op++) {
val=val.toString();
// перебираем число посимвольно, как строку
for (var iMax=val.length-1, i=iMax, j=0, digSum=0, arrSum=[], carry=0; i>=0 && j<=iMax; i--, j++) {
// складываем цифры с обоих концов + перенос из предыдущего разряда
digSum = parseInt(val[i])+parseInt(val[j])+carry;
// если сумма больше 9
if (digSum>9) {
// в массив закидываем только разряд до 10
arrSum[arrSum.length]=digSum-10;
// делаем перенос в следующий разряд
carry=1;
// финальный перенос
if (i==0) arrSum[arrSum.length]=1;
} else {
arrSum[arrSum.length]=digSum;
carry=0;
}
}
val = arrSum.join("");
// если перевернутая сумма равна сама себе
if (val == val.split("").reverse().join("")) {
// получили палиндром - прерываем
palindrome = true;
break;
}
}
// если до палиндрома так и не дошло - считаем
if (!palindrome) {
count++;
}
}
return count;
}В итоге, количество положительных натуральных чисел меньших maxNum = 13110 таких, что из них нельзя получить палиндром за 50 операций: 359.
Задача 5
Рассмотрим все возможные числа ab для 1<a<6 и 1<b<6:
22=4, 23=8, 24=16, 25=32 32=9, 33=27, 34=81, 35=243, 42=16, 43=64, 44=256, 45=1024, 52=25, 53=125, 54=625, 55=3125
Если убрать повторения, то получим 15 различных чисел.
Сколько различных чисел ab для 2<a<149 и 2<b<121?
Решение 5
В приведенном выше примере совпали варианты 24=16 и 42=16, т.к. 42 можно представить, как (2*2)2 => 22*2 => 24. Поэтому, чтобы не возводить все в степени, можно просто привести все a к степени простого числа, например: 16 = 24, 27 = 33, 125 = 53 и т.д.
// функция определения степени числа
function isPowerOf(val,prime){
var power = 0;
// если число делится без остатка на простое число
if (val%prime == 0) {
// делим пока
while ((val/=prime)>=1) {
power++;
if (val==1) return power;
}
}
return 0;
}
Требуемый для вычислений ряд простых чисел можно определить функцией из выше рассмотренной Задачи 2, но для упрощения в данном случае возьмем готовые значения. При чем, достаточно взять первые несколько чисел (2, 3, 5, 7, 11), где максимальное простое число будет не более квадратного корня из a, т.к. для данного случая мы не сможем разложить a < 149 на степени 13: 132 > 149.
Перебирая ряд простых чисел, определяем, можно ли представить число a степенью. А полученную степень просто перемножаем с соответствующими b. Из результата задаем очередной ассоциативный индекс idx для массива всех вариаций ab (arr), например:
3100 => a3b100
и 950 => 32*50 => 3100 => a3b100
Соответственно, проверяем наличие элемента с данным индексом в массиве arr.
Итоговая функция подсчета, где a1, b1 — соответствующие минимумы входных значений, и a2, b2 — максимумы входных значений:
// a1, b1 - соответствующие минимумы входных значений, и a2, b2 - максимумы входных значений
function task5(a1,a2,b1,b2) {
for (var a=a1+1, arr=[], power=1, count=0; a<a2; a++){
// определим ряд простых чисел
var primes = [2,3,5,7,11];
// перебирая ряд простых чисел, определяем, можно ли представить число степенью
for (var i=0; i < primes.length; i++) {
power = isPowerOf(a,primes[i]);
if (power>1) {
break;
}
}
for (var b=b1+1, idx=''; b<b2; b++){
// зададим очередной ассоциативный индекс для массива всех вариаций a в степени b
idx = (power>1)? "a"+primes[i]+"b"+power*b : "a"+a+"b"+b ;
// если такого индекса в массиве еще не было
if (!arr[idx]) {
// заполняем новый элемент значением
arr[idx]=1;
// считаем итоговые уникальные индексы
count++;
}
}
}
return count;
}
Для 2<a<149 и 2<b<121 различных чисел ab: 16529.
Задача 6
В некоторых числах можно найти последовательности цифр, которые в сумме дают 10. К примеру, в числе 3523014 целых четыре таких последовательности:
3523014
3523014
3523014
3523014
Можно найти и такие замечательные числа, каждая цифра которых входит в по крайней мере одну такую последовательность.
Например, 3523014 является замечательным числом, а 28546 — нет (в нём нет последовательности цифр, дающей в сумме 10 и при этом включающей 5).
Найдите количество этих замечательных чисел в интервале [1, 1900000] (обе границы — включительно).
Решение 6
Единственное решение для этой задачи, которое мне пришло в голову — прямой перебор. Но я постарался его максимально оптимизировать.
Каждое число num будем разбивать на массив цифр arrPrep, исключая из него все нули, т.к. они никакой роли не играют.
Для начала можем проверить сумму сразу всех цифр sum:
- если равна 10 — т.е. число представляет из себя максимальную последовательность и его можно сразу отнести к замечательным;
- если меньше 10 — число не имеет ни одной последовательности и не является замечательным;
Далее можем сразу проверить первые две и последние две цифры. Если хотя бы одна из пар в сумме больше 10 — число точно не является замечательным, например: 56112, 127379.
Теперь можно приступить к перебору всех последовательностей.
Суммы последовательностей будут записываться в двумерный массив s. Основную диагональ которого предварительно заполним всеми цифрами из arrPrep.
Если найдена удачная последовательность — заполняем проверочный массив arrCheck цифрами, входящими в данную последовательность.
В конце сравним строчные представления массива arrPrep и проверочного массива arrCheck. Если равны — все цифры числа использованы хотя бы в одной удачной последовательности — т.е. число замечательное.
// функция определения "замечательного" числа
function isWonderful(num) {
var arrRaw=[], arrPrep=[], len=0, sum=0;
// разберем число на массив цифр
arrRaw = num.toString().split("");
for (var i=0, digit=0; i<arrRaw.length; i++){
digit=parseInt(arrRaw[i]);
// исключаем нули
if (digit>0) {
arrPrep[arrPrep.length]=digit;
// сумма всех цифр числа
sum+=digit;
}
}
// длина обработанного массива цифр
len=arrPrep.length;
// если сумма всех цифр числа равна 10, число - "замечательное"
if (sum==10) {
return true;
// сумма всех цифр числа меньше 10 - не является "замечательным"
} else if (sum<10) {
return false;
} else {
// если первые 2 или последние 2 цифры в сумме больше 10 - не является "замечательным"
if ((arrPrep[0]+arrPrep[1])>10 || (arrPrep[len-1]+arrPrep[len-2])>10) {
return false;
}
for (var i=0, s=[]; i<len; i++){
// задаем двумерный массив для хранения сумм последовательностей
s[i]=[];
// заполняем диагональ массива цифрами числа
s[i][i]=arrPrep[i];
}
// перебираем последовательности цифр
for (var i=0, arrCheck=[]; i<len-1; i++){
for (var j=i; j<len-1; j++){
// сумма очередной последовательности
s[i][j+1]=s[i][j]+s[j+1][j+1];
// нашли удачную последовательность
if (s[i][j+1]==10){
for (var k=i;k<=j+1;k++){
// заполняем проверочный массив цифрами, уже использованные хотя бы в одной удачной последовательности
arrCheck[k]=s[k][k];
}
break;
// перебор - ищем следующую последовательность
} else if (s[i][j+1]>10) {
break;
}
}
}
// сравниваем строчные представления обработанного массива цифр и проверочного массива
if (arrPrep.join('')==arrCheck.join('')) {
// все цифры числа использованы хотя бы в одной удачной последовательности - число "замечательное"
return true;
}
}
return false;
}
// функция подсчета "замечательных" чисел в интервале x1, x2
function task6(x1,x2) {
for (var x=x1, count=0; x<=x2; x++){
// если число "замечательное" - считаем
if (isWonderful(x)) {
count++;
}
}
return count;
}
Количество замечательных чисел в интервале [1, 1900000]: 152409.
Комментарии (30)
CrazyOpossum
11.10.2016 14:58Задача 3: интересный факт, дроби n/7 имеют периоды (7-1) в десятичной записи и они получаются перестановкой цифр для разных n. Если не ошибаюсь, то же верно и для 17 с периодом (17-1). Короче, увлекающиеся подобной фигнёй решают эту задачу в уме.
max0ua
12.10.2016 10:26Решал без непосредственных вычислений такую задачу в школьные годы: «Найти шестизначное число которое при умножении на 2, 3, 4, 5, 6 дает в результате шестизначное число записанное теми же цифрами что и исходное но в другом порядке.»
N = 142857 2N = 285714 3N = 428571 4N = 571428 5N = 714285 6N = 857142
Large
12.10.2016 14:47И это более правильный подход, в решении никак не используется ограничение на первую цифру (1-3) в вашем случае она детерминировано 1.
wizarts
12.10.2016 15:57В решении сравниваются именно строчные значения, а не сами числа. Поэтому для гипотетического случая с 0 (далее числа выдуманы): для x = 123450 могли бы получить 2*x=254130 и 3*x=351240, где строчные значения всех этих чисел равны «012345».
Large
12.10.2016 17:14for (var x=1, xSorted=''; x<=1000000; x++) — тут вы зачем проверяете число которое с 4 начинается? Если число х начинается с 4, то 3*x будет большей длины чем х и проверять этот случай смысла нет (даже такие случаи 4, 34, 334 и т.д.)
wizarts
12.10.2016 19:26Согласен, спасибо. Т.к. 4 — частный случай для данных входных значений, добавил в решение расчет максимума первой цифры x. Т.е., например, для варианта 2*x, 4*x — xFirstMax уже будет 2, а для 3*x, 7*x — xFirstMax = 1.
Stelet
11.10.2016 17:00В задаче 4 где-то ошибка, возможно, в ParseInt или при сравнении строк и чисел, не знаю JS. Проверил для одного лишнего числа 10548, где-то на 30 итерации получилось число 17858768886785871. В консоли Хрома это число не присваивается переменной, при присвоении получается 17858768886785872. Возможно, ошибка в этом.
У меня получился ответ 359, вот те 9 лишних чисел в вашем решении: [10548, 10794, 10828, 11538, 11784, 11818, 12528, 12774, 12808].wizarts
14.10.2016 18:17Переписал решение для 4-ой задачи. Теперь суммируем не целые числа, а посимвольно строки — работает даже быстрее. Действительно, верный ответ 359.
lismut
12.10.2016 09:24В задаче №3 говорится про перестановку цифр чисел 2х и 3х, про цифры самого х ничего не сказано, так что предполагаю, что ответ 1782 (2*1782 = 3564, 3*1782 = 5346)
dm_p2016
12.10.2016 09:25В задаче 3 формулировка вводит в заблуждение. Написано, что «числа 2*x, 3*x можно получить друг из друга перестановкой цифр». Однако, судя по решению, требуется найти натуральное x такое, что числа x, 2*x, 3*x можно получить друг из друга перестановкой цифр.
wizarts
12.10.2016 10:23Да, формулировка действительно странновата. Просто тогда не ясен смысл умножения на 2. Можно было бы тогда просто найти x, из которого надо получить число 1.5*х перестановкой цифр.
drch
12.10.2016 09:25Немного не понял решение 6-ой задачи. Ведь если речь идет о последовательностях, то достаточно начать складывать все цифры числа — если на каком-то шаге у нас будет сумма больше 10 — то это не замечательное число, а если же на последнем шаге итерации у нас сумма 10 — то число замечательное.
foo = function(n) { n = n.toString(); n = n.slice(''); for(var i = 0, sum = 0; i<n.length; i++) { sum += parseFloat(n[i], 10); if(sum==10 && i == (n.length-1)) { return true; } if(sum>10) { return false; } else { if(sum==10) { sum = 0; } } } return false; }wizarts
12.10.2016 09:41Сумма всех цифр числа, равная 10, — частный случай задачи, учитываемый в одном из этапов моего решения.
Обратите внимание на пример в самом задании. Последовательностью является не только та, что начинается с первой цифры:
3523014
3523014
3523014drch
12.10.2016 10:04Но ведь в замечательном числе все цифры являются частями последовательностей, разве я не прав?
urakin
12.10.2016 11:10Например, решение задачи 5 (остальные пока не смотрел) — не верно. Оно не учитывает сочетания степеней простых чисел, поэтому результат завышен.
Вот моя программа, которая не анализирует, а решает «в лоб»:
import java.math.BigInteger;
import java.util.LinkedList;
public class Task3 {
public static void main(String[] args) {
int minA = 3;
int maxA = 148;
int minB = 3;
int maxB = 120;
LinkedList numbers = new LinkedList<>();
for (int i = minA; i <= maxA; i++) {
for (int b = minB; b <= maxB; b++) {
BigInteger a = new BigInteger(String.valueOf(i));
a = a.pow(b);
if (!numbers.contains(a)) {
numbers.add(a);
}
}
}
System.out.println(numbers.size());
}
}
Да, не эффективно по ресурсам на вычисление, зато очень даже эффективно, чтобы понять, что 16529 — ответ не верный. Верный — 16355.
eandr_67
Задача N 1.
1*d + 2*d +… + (n-1)*d + n*d = s*d, гд s — банальная сумма арифметической прогрессии, изучаемая в школе:
s = (1+n)*n/2
Значие n также находится простейшим вычислением.
Вывод: задача элементарно решается вообще без циклов.
wizarts
Это было бы справедливо, если бы d не менялось на следующем витке.
eandr_67
Сумма квадратичной последовательности есть кубическая функция. Так что цикл всё равно не нужен, но формула будет чуть сложнее. Для нечётных size формула:
wizarts
Справедливо, «плюсую».
Jojat
Можете описать, как вы пришли к этой формуле?
alexeykuzmin0
Я в свое время в школе нашел ее примерно следующими рассуждениями:
1. Понятно, что сумма квадратов — кубическая формула: S(n) = an^3 + bn^2 + cn + d.
2. Запишем систему уравнений для небольших n, чтобы найти a, b, c, d:
1 = a + b + c + d
5 = 8a + 4b + 2c + d
14 = 27a + 9b + 3c + d
30 = 64a + 16b + 4c + d
3. Решим, найдем a, b, c, d.
wizarts
Добавил как альтернативное решение. Да, хотелось бы немного подробнее описание вывода формулы.
eandr_67
Искал коэф-ты «в лоб» — методом наименьших квадратов.