Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 69
тривиальная задача.
Уважаемые минусующие!
Идите лесом!
Задачка решается на БУМАГЕ, за 3 МИНУТЫ, имеет множество решений, так же как и множество вариантов этой задачи!
тоесть задача может быть например не abcde * 2 = bcdea, а abcde * 3 = bcdea или *5, и тоже будет иметь решение.
Вот одно из чисел — которое я получил на БУМАГЕ за 2 минуты.
105 263 157 894 736 842
Идите лесом!
Задачка решается на БУМАГЕ, за 3 МИНУТЫ, имеет множество решений, так же как и множество вариантов этой задачи!
тоесть задача может быть например не abcde * 2 = bcdea, а abcde * 3 = bcdea или *5, и тоже будет иметь решение.
Вот одно из чисел — которое я получил на БУМАГЕ за 2 минуты.
105 263 157 894 736 842
Реально круто. А можете объяснить ход решения?
Можете найти здесь, к примеру: inf.1september.ru/article.php?ID=200702301
круто.
но у вас получилось число в два раза больше, а по условию нужно получить в два раза меньше
но у вас получилось число в два раза больше, а по условию нужно получить в два раза меньше
ПОчему не удовлетворяет? abcde это только чтобы принцип был понят, а так мог я написать и abc и abcdefghikl
Да-да-… я ошибся… Извиняйте. число для «минуса» будет 2 105 263 157 894 736 842
Ну abcde можно представить как 10000a+1000b+100c+10d+e
bcdea как 10000b+1000c+100d+10e+a
Получили
20000a+2000b+200c+20d+2e=10000b+1000c+100d+10e+a
19999a-8000b-800c-80d-8e=0
Получается диофантово уравнение, а в случае с произвольной разрялностью, оно похоже не имеет решения в общем виде.
bcdea как 10000b+1000c+100d+10e+a
Получили
20000a+2000b+200c+20d+2e=10000b+1000c+100d+10e+a
19999a-8000b-800c-80d-8e=0
Получается диофантово уравнение, а в случае с произвольной разрялностью, оно похоже не имеет решения в общем виде.
чето проглючило. вот еще ссылка:
ru.wikipedia.org/wiki/Десятая_проблема_Гильберта
ru.wikipedia.org/wiki/Десятая_проблема_Гильберта
В двоичной системе 01 и 10
0.
Если задача про дяситичную систему, то решения нет.
Действительно, по условию задачи должно быть:
10*a+b = 2*(b*10^n+a), где b — цифра, a — любое число, а n — количество цифр в a.
Тогда получим b*(2*10^n-1)=8*a,
но так как 2*10^n-1 на 2 не делится, то b должно делится на 8, т.е. равнятся 8, а значит a должно равняться 2*10^n-1. В последнем числе, очевидно, n+1 цифр, а в a — n, следовательно, равенство никогда не выполняется.
Действительно, по условию задачи должно быть:
10*a+b = 2*(b*10^n+a), где b — цифра, a — любое число, а n — количество цифр в a.
Тогда получим b*(2*10^n-1)=8*a,
но так как 2*10^n-1 на 2 не делится, то b должно делится на 8, т.е. равнятся 8, а значит a должно равняться 2*10^n-1. В последнем числе, очевидно, n+1 цифр, а в a — n, следовательно, равенство никогда не выполняется.
Вот так и непонятно, одни говорят «тривиальная задача», другие что ее вообще невозможно решить. Так есть «официальная версия решения» :)?
int исчерпан :(
перевожу на long
перевожу на long
мдя, я лет 100500 так считать буду. сейчас переведу на BigInteger (теоретически бесконечное число) и пусть кто-нибудь, кто располагает большими выч. мощностями стучит в личку :-D
готово, ну что, у кого есть сервер с INTEL QUADx8 128 GB RAM с jvm? )
слабовата у вас скорость перебора. Я довёл до 420 миллионов проверок в секунду на одном ядре, примерно 8,6 такта процессора на проверку одного числа. Инт ущитывается весь за несколько секунд, а вот 8ми байтовой целое будет считаться очень долго, чтобы найти число которое приведено в комментариях мне потребуется 8 лет. Я конечно еще на 25% разгонял брутер, но она некрасивый по коду получается. Ну многопоточность, даже на 16 ядрах будем пол года считать до первого числа. А уж о выявлении всех таких чисел даже в диапазоне 8ми байт я просто молчу
В двоичной системе исчисления умножение на 2 делается как раз сдвигом влево.
Что-то у меня получилось что нет целочисленного решения :)
abcde*2 = bcdea
2(10000a + 1000b + 100c + 10d + e )=10000b+ 1000c + 100d + 10e + a
20000a + 2000b + 200c + 20d + 2e = 10000b+ 1000c + 100d + 10e + a
a=20000a + 2000b + 200c + 20d + 2e-10000b-1000c — 100d — 10e
-19999a = 2000b + 200c + 20d + 2e-10000b-1000c — 100d — 10e
a=(2000b + 200c + 20d + 2e-10000b-1000c — 100d — 10e)/-19999
a=(8000b + 800c +80d + 8e)/19999
19999a=8*bcde
19999*a/8=bcde
a может изменяться в пределах от 0 до 4 включительно (иначе bcdea было бы больше на порядок)
Чисел от 0 до 4, которые, будучи помноженными на 2499,875 (это 19999/8) давали бы целочисленный результат я не знаю :)
bcde=19999*a/8
abcde*2 = bcdea
2(10000a + 1000b + 100c + 10d + e )=10000b+ 1000c + 100d + 10e + a
20000a + 2000b + 200c + 20d + 2e = 10000b+ 1000c + 100d + 10e + a
a=20000a + 2000b + 200c + 20d + 2e-10000b-1000c — 100d — 10e
-19999a = 2000b + 200c + 20d + 2e-10000b-1000c — 100d — 10e
a=(2000b + 200c + 20d + 2e-10000b-1000c — 100d — 10e)/-19999
a=(8000b + 800c +80d + 8e)/19999
19999a=8*bcde
19999*a/8=bcde
a может изменяться в пределах от 0 до 4 включительно (иначе bcdea было бы больше на порядок)
Чисел от 0 до 4, которые, будучи помноженными на 2499,875 (это 19999/8) давали бы целочисленный результат я не знаю :)
bcde=19999*a/8
Простите, цифр*
Вы, как и многие здесь, не обратили внимание на «разрядность не ограничена», а почему-то решили что число пятизначное)
Суть задачи: найти число, которое, если взять последнюю цифру...
В моем понимании цифра это 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Все что больше — Числа.
http://ru.wikipedia.org/wiki/Цифр
А про разрядность да, не углядел.
В моем понимании цифра это 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Все что больше — Числа.
http://ru.wikipedia.org/wiki/Цифр
А про разрядность да, не углядел.
Разрядность не имеет значения.
Число разрядности n представимо полиномом вида
a*10n + b*10n-1 + c*10n-2 +… + y*101 + z
Перенесем первую цифру и запишем полученное число в виде полинома
b*10n + c*10n-1 + d*10n-2 +… + z*101 + a
Составим уравнение
2a*10n + 2b*10n-1 + 2c*10n-2 +… + 2y*101 + 2z = b*10n + c*10n-1 + d*10n-2 +… + z*101 + a
a(2*10n – 1) = b*10n-1 * 8 + c*10n-2 * 8 + d*10n-3 * 8 +… + z * 8
Выносим восьмерки
a(2*10n – 1) = 8( b*10n-1 + c*10n-2 + d*10n-3 +… + z)
a = 8 *(b*10n-1 + c*10n-2 + d*10n-3 +… + z) / (2*10n – 1)
И полученное число должно быть натуральным, от 0 до 9.
Число в знаменателе, очевидно, будет представлять собой единицу и n девяток.
Забудем на время про восьмерку, посмотрим на оставшуюся часть дроби. Степень знаменателя, как видно, больше степени числителя. Т.е. дробь правильная, ее значение лежит на интервале [0,.5). Получить целое число можно с помощью восьмерки (Кстати, оно должно быть меньше 4 ввиду правой границы интервала).
Что может дать нам девятку в конце числа? Умножение 7 на 7, 1 на 9, 9 на 1 или 3 на 3. То есть, частное (если нам удастся поделить знаменатель на числитель) будет оканчиваться на 1, 3, 7 или 9. Внимание,
вопрос: какое число, оканчивающееся на любую из этих цифр, будет делиться на 8 без остатка?
Число разрядности n представимо полиномом вида
a*10n + b*10n-1 + c*10n-2 +… + y*101 + z
Перенесем первую цифру и запишем полученное число в виде полинома
b*10n + c*10n-1 + d*10n-2 +… + z*101 + a
Составим уравнение
2a*10n + 2b*10n-1 + 2c*10n-2 +… + 2y*101 + 2z = b*10n + c*10n-1 + d*10n-2 +… + z*101 + a
a(2*10n – 1) = b*10n-1 * 8 + c*10n-2 * 8 + d*10n-3 * 8 +… + z * 8
Выносим восьмерки
a(2*10n – 1) = 8( b*10n-1 + c*10n-2 + d*10n-3 +… + z)
a = 8 *(b*10n-1 + c*10n-2 + d*10n-3 +… + z) / (2*10n – 1)
И полученное число должно быть натуральным, от 0 до 9.
Число в знаменателе, очевидно, будет представлять собой единицу и n девяток.
Забудем на время про восьмерку, посмотрим на оставшуюся часть дроби. Степень знаменателя, как видно, больше степени числителя. Т.е. дробь правильная, ее значение лежит на интервале [0,.5). Получить целое число можно с помощью восьмерки (Кстати, оно должно быть меньше 4 ввиду правой границы интервала).
Что может дать нам девятку в конце числа? Умножение 7 на 7, 1 на 9, 9 на 1 или 3 на 3. То есть, частное (если нам удастся поделить знаменатель на числитель) будет оканчиваться на 1, 3, 7 или 9. Внимание,
вопрос: какое число, оканчивающееся на любую из этих цифр, будет делиться на 8 без остатка?
Никакое, так как 8 четное, а 1,3,7,9 нечетные, а значит и числа будут тоже нечетными)
Нечетные на четные не делятся.
Нечетные на четные не делятся.
Не понятно только, зачем нам нужна девятка в конце числа?
Можно пойти по-другому:
a*10n + b = 2*(b*10+a)
a = {0,2,4,6,8}
b — целое число
отсюда
b = (10n-2)*a/19
остается найти число 10n-2, которое делится на 19. И такие числа существуют(по крайней мере одно). Другое дело, что на бумаге я его найти не смогу =)
Можно пойти по-другому:
a*10n + b = 2*(b*10+a)
a = {0,2,4,6,8}
b — целое число
отсюда
b = (10n-2)*a/19
остается найти число 10n-2, которое делится на 19. И такие числа существуют(по крайней мере одно). Другое дело, что на бумаге я его найти не смогу =)
Суть задачи: найти число, которое, если взять последнюю цифру и переместить в начало будет в два раза меньше получившегося числа. То есть, abcde * 2 = bcdea. Разрядность не ограничена.
abcde * 2 = bcdea — первая цифра в конец.
abcde * 2 = eabcd — последняя в начало.
Написал програмку которая брутит. Запустил и жду…
Вот если кто то хочет довести до конца — вот код.
Вот если кто то хочет довести до конца — вот код.
- public class Main {
- public static int digits(long number) {
- int count = 0;
- while (number != 0) {
- number /= 10;
- count++;
- }
- return count;
- }
- public static boolean check(long number, boolean debug) {
- if(debug)
- System.out.println("Completed " + number + " numbers");
- long last = number % 10;
- if(last % 10 == 0)
- return false;
- long res = number/10+last*(long)Math.pow(10, digits(number)-1);
- return number*2 == res;
- }
- public static void main(String[] args) {
- for(long i=0;i<Long.MAX_VALUE;i++) {
- boolean c = check(i, i%10000000==0);
- if(c) {
- System.out.println(i);
- break;
- }
- }
- }
- }
Решение на пхп:
<?php
$a = 2;
$source = array($a*2);
$modified = array($a);
$add = 0;
do
{
$newDigit = $source[0] * 2 + $add;
$add = 0;
if($newDigit > 9)
{
$newDigit = $newDigit % 10;
$add = 1;
}
array_unshift($source, $newDigit);
}
while(!check($source, $a));
echo implode('', $source);
function check($source, $a)
{
$modified = array_merge(array_slice($source, 1, count($source)), array($source[0]));
$add = 0;
for($i=count($modified)-1;$i>=0;$i--)
{
$d = $modified[$i] * 2 + $add;
$add = 0;
if($d > 9)
{
$d = $d % 10;
$add = 1;
}
if($d != $source[$i])
return false;
}
if($add == 0)
return true;
else
return false;
}
?>
<?php
$a = 2;
$source = array($a*2);
$modified = array($a);
$add = 0;
do
{
$newDigit = $source[0] * 2 + $add;
$add = 0;
if($newDigit > 9)
{
$newDigit = $newDigit % 10;
$add = 1;
}
array_unshift($source, $newDigit);
}
while(!check($source, $a));
echo implode('', $source);
function check($source, $a)
{
$modified = array_merge(array_slice($source, 1, count($source)), array($source[0]));
$add = 0;
for($i=count($modified)-1;$i>=0;$i--)
{
$d = $modified[$i] * 2 + $add;
$add = 0;
if($d > 9)
{
$d = $d % 10;
$add = 1;
}
if($d != $source[$i])
return false;
}
if($add == 0)
return true;
else
return false;
}
?>
С++-прогеры, напишите свое решение! жаба и пых очень медленные )
Суть задачи: найти число, которое, если взять последнюю цифру и переместить в начало будет в два раза меньше получившегося числа. То есть, abcde * 2 = bcdea
Сказали одно, пример привели не тот=)
Если число в 2 раза меньше получившегося, то bcdea * 2 = abcde. Или, чтоб понятнее, abcde * 2 = eabcd
Кстати, если моя логика меня не подводит, задача вида abc… * 2 = bc...a не решается.
еще задачка:
найдите число, сумма цифр которого равна этому числу )
найдите число, сумма цифр которого равна этому числу )
105263157894736842
157894736842105263
210526315789473684
263157894736842105
315789473684210526
368421052631578947
421052631578947368
473684210526315789
Ударим мозгами по брутфорсу же!
157894736842105263
210526315789473684
263157894736842105
315789473684210526
368421052631578947
421052631578947368
473684210526315789
Ударим мозгами по брутфорсу же!
да черт возьми же, выложите решение !
shaman4d.habrahabr.ru/blog/93370/#comment_2833220
101, 102,…, 1018 все имеют различные остатки от деления на 19, и дальше эта последовательность повторяется с периодом 18. В частности, остаток 2 имеют степени 1017, 1035 и т.д. Остается подобрать такое (четное) a, чтобы 10n < b < 10n-1 — 2,4,6,8:
105263157894736842
210526315789473684
315789473684210526
421052631578947368
Числа большей разрядности можно получить простым повторением этих:
105263157894736842105263157894736842105263157894736842 * 2 = 210526315789473684210526315789473684210526315789473684
101, 102,…, 1018 все имеют различные остатки от деления на 19, и дальше эта последовательность повторяется с периодом 18. В частности, остаток 2 имеют степени 1017, 1035 и т.д. Остается подобрать такое (четное) a, чтобы 10n < b < 10n-1 — 2,4,6,8:
105263157894736842
210526315789473684
315789473684210526
421052631578947368
Числа большей разрядности можно получить простым повторением этих:
105263157894736842105263157894736842105263157894736842 * 2 = 210526315789473684210526315789473684210526315789473684
a не обязательно чётное. Так правильнее: a = [2; 9]
ну тогда уже a = [0,4];
Когда а >= 5 при умножении на 2 количество разрядов у числа увеличится. А при нуле вполне себе может существовать решение.
Когда а >= 5 при умножении на 2 количество разрядов у числа увеличится. А при нуле вполне себе может существовать решение.
задачку эту решал еще в пятом или шестом классе на олимпиаде по математике, решил таки :) решение находится алгритмически просто :)
У меня вышло, что решения не может существовать.
если представить число так
(a*m + b) * 2= b*10 + a, где m число вида 10^x, где x натуральное число.
1. если a >= 5 при умножении на 2 количество разрядов поменяется.
2. a != 0, т.к. 2*b != 10*b
Значит a = [1, 2, 3, 4]
если перенести члены, то получается
a*(2m-1)/8 = b
2m-1 всегда будет вида 19, 199, 1999, а a меньше 8, тоесть целочисленное b невозможно.
если представить число так
(a*m + b) * 2= b*10 + a, где m число вида 10^x, где x натуральное число.
1. если a >= 5 при умножении на 2 количество разрядов поменяется.
2. a != 0, т.к. 2*b != 10*b
Значит a = [1, 2, 3, 4]
если перенести члены, то получается
a*(2m-1)/8 = b
2m-1 всегда будет вида 19, 199, 1999, а a меньше 8, тоесть целочисленное b невозможно.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача