Комментарии 69
тривиальная задача.
+6
Уважаемые минусующие!
Идите лесом!
Задачка решается на БУМАГЕ, за 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
+17
Реально круто. А можете объяснить ход решения?
0
Можете найти здесь, к примеру: inf.1september.ru/article.php?ID=200702301
0
круто.
но у вас получилось число в два раза больше, а по условию нужно получить в два раза меньше
но у вас получилось число в два раза больше, а по условию нужно получить в два раза меньше
0
НЛО прилетело и опубликовало эту надпись здесь
ПОчему не удовлетворяет? abcde это только чтобы принцип был понят, а так мог я написать и abc и abcdefghikl
-1
Да-да-… я ошибся… Извиняйте. число для «минуса» будет 2 105 263 157 894 736 842
0
Ну 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
Получается диофантово уравнение, а в случае с произвольной разрялностью, оно похоже не имеет решения в общем виде.
+4
чето проглючило. вот еще ссылка:
ru.wikipedia.org/wiki/Десятая_проблема_Гильберта
ru.wikipedia.org/wiki/Десятая_проблема_Гильберта
+1
НЛО прилетело и опубликовало эту надпись здесь
В двоичной системе 01 и 10
+20
НЛО прилетело и опубликовало эту надпись здесь
0.
+3
Если задача про дяситичную систему, то решения нет.
Действительно, по условию задачи должно быть:
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, следовательно, равенство никогда не выполняется.
-3
Вот так и непонятно, одни говорят «тривиальная задача», другие что ее вообще невозможно решить. Так есть «официальная версия решения» :)?
0
int исчерпан :(
перевожу на long
перевожу на long
+4
мдя, я лет 100500 так считать буду. сейчас переведу на BigInteger (теоретически бесконечное число) и пусть кто-нибудь, кто располагает большими выч. мощностями стучит в личку :-D
-1
готово, ну что, у кого есть сервер с INTEL QUADx8 128 GB RAM с jvm? )
+4
слабовата у вас скорость перебора. Я довёл до 420 миллионов проверок в секунду на одном ядре, примерно 8,6 такта процессора на проверку одного числа. Инт ущитывается весь за несколько секунд, а вот 8ми байтовой целое будет считаться очень долго, чтобы найти число которое приведено в комментариях мне потребуется 8 лет. Я конечно еще на 25% разгонял брутер, но она некрасивый по коду получается. Ну многопоточность, даже на 16 ядрах будем пол года считать до первого числа. А уж о выявлении всех таких чисел даже в диапазоне 8ми байт я просто молчу
0
В двоичной системе исчисления умножение на 2 делается как раз сдвигом влево.
0
Что-то у меня получилось что нет целочисленного решения :)
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
-1
Простите, цифр*
0
Вы, как и многие здесь, не обратили внимание на «разрядность не ограничена», а почему-то решили что число пятизначное)
+1
Суть задачи: найти число, которое, если взять последнюю цифру...
В моем понимании цифра это 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/Цифр
А про разрядность да, не углядел.
0
Разрядность не имеет значения.
Число разрядности 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 без остатка?
0
Никакое, так как 8 четное, а 1,3,7,9 нечетные, а значит и числа будут тоже нечетными)
Нечетные на четные не делятся.
Нечетные на четные не делятся.
0
Не понятно только, зачем нам нужна девятка в конце числа?
Можно пойти по-другому:
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. И такие числа существуют(по крайней мере одно). Другое дело, что на бумаге я его найти не смогу =)
+2
Суть задачи: найти число, которое, если взять последнюю цифру и переместить в начало будет в два раза меньше получившегося числа. То есть, abcde * 2 = bcdea. Разрядность не ограничена.
abcde * 2 = bcdea — первая цифра в конец.
abcde * 2 = eabcd — последняя в начало.
-1
Написал програмку которая брутит. Запустил и жду…
Вот если кто то хочет довести до конца — вот код.
Вот если кто то хочет довести до конца — вот код.
- 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;
- }
- }
- }
- }
+1
Решение на пхп:
<?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;
}
?>
+3
С++-прогеры, напишите свое решение! жаба и пых очень медленные )
0
Суть задачи: найти число, которое, если взять последнюю цифру и переместить в начало будет в два раза меньше получившегося числа. То есть, abcde * 2 = bcdea
Сказали одно, пример привели не тот=)
Если число в 2 раза меньше получившегося, то bcdea * 2 = abcde. Или, чтоб понятнее, abcde * 2 = eabcd
Кстати, если моя логика меня не подводит, задача вида abc… * 2 = bc...a не решается.
0
еще задачка:
найдите число, сумма цифр которого равна этому числу )
найдите число, сумма цифр которого равна этому числу )
-1
105263157894736842
157894736842105263
210526315789473684
263157894736842105
315789473684210526
368421052631578947
421052631578947368
473684210526315789
Ударим мозгами по брутфорсу же!
157894736842105263
210526315789473684
263157894736842105
315789473684210526
368421052631578947
421052631578947368
473684210526315789
Ударим мозгами по брутфорсу же!
+2
да черт возьми же, выложите решение !
-1
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
0
a не обязательно чётное. Так правильнее: a = [2; 9]
+1
ну тогда уже a = [0,4];
Когда а >= 5 при умножении на 2 количество разрядов у числа увеличится. А при нуле вполне себе может существовать решение.
Когда а >= 5 при умножении на 2 количество разрядов у числа увеличится. А при нуле вполне себе может существовать решение.
+1
Вы путаете задачи. Внимательней почитайте комментарии, автор допустил ошибку при написании топика.
0
То, что есть другая задача, я знаю. Очень много других задач. Но ведь обсуждение идет именно этой задачи, разве нет? И применительно к ней мое замечание тоже действительно.
0
задачку эту решал еще в пятом или шестом классе на олимпиаде по математике, решил таки :) решение находится алгритмически просто :)
+1
У меня вышло, что решения не может существовать.
если представить число так
(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 невозможно.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача