for($x = 0; ; $x++)
{
$k = 2*pow10mod19($x) - 4;
print $x, " => ", $k % 19, "\n";
if($k % 19 == 0)
{
print "Найдено: ", $x, "\n";
last;
}
}
sub pow10mod19
{
my($k) = @_;
my $m = 1;
for(my $i = 1; $i <= $k; $i++)
{
$m = ($m * 10) % 19;
}
return $m;
}
[миниконкурс] "Двойка"
Простенькая задачка: есть число, которое заканчивается на 2, если переставить 2-ку в начало этого числа - то получится число в два раза большее, найти исходное число.
Предлагайте решения в виде кода (желательно с описанием алгоритма). Будем выбирать самое оригинальное. Хотя вариантов IMHO мало... :)
Призы, как обычно,- зелененькие квадратики... :)
Предлагайте решения в виде кода (желательно с описанием алгоритма). Будем выбирать самое оригинальное. Хотя вариантов IMHO мало... :)
Призы, как обычно,- зелененькие квадратики... :)
Цитата: Green
Призы, как обычно,- зелененькие квадратики... :)
в свете последних событий - звучит как провокация
Ну ладно... тогда обойдемся без приза...
если можно, уточните:
допустим было 102, после перестановки получается 210 ?
в таком случае в цикле while (float результат_деления!=2)
делается счетчик i++
далее число переводится в строку, подставляем в одну переменную AnsiString "2" вначале а в другую в конце
переводим их StrToInt делим большее на меньшее, смотрим результат
как цикл закончился во 2-й переменной как раз и будет искомое число
допустим было 102, после перестановки получается 210 ?
в таком случае в цикле while (float результат_деления!=2)
делается счетчик i++
далее число переводится в строку, подставляем в одну переменную AnsiString "2" вначале а в другую в конце
переводим их StrToInt делим большее на меньшее, смотрим результат
как цикл закончился во 2-й переменной как раз и будет искомое число
K*10 + 2 - исходное число
2*(10^X) + K - число после перестановки
2*(K*10 + 2) = 2*(10^X) + K
19*K = 2*(10^X) - 4
Решение задачи сводится к нахождению такого целого X, при котором
(2*(10^X) - 4) mod 19 = 0.
Ответ находим при X=17. Т.е. K = (2*(10^17) - 4) / 19
Искомое число: 10 * (2*(10^17) - 4) / 19 + 2
Такие же результаты получаем для:
17
35
53
71
89
107
...
Таких чисел много.
2*(10^X) + K - число после перестановки
2*(K*10 + 2) = 2*(10^X) + K
19*K = 2*(10^X) - 4
Решение задачи сводится к нахождению такого целого X, при котором
(2*(10^X) - 4) mod 19 = 0.
Код:
Ответ находим при X=17. Т.е. K = (2*(10^17) - 4) / 19
Искомое число: 10 * (2*(10^17) - 4) / 19 + 2
Такие же результаты получаем для:
17
35
53
71
89
107
...
Таких чисел много.
То же самое на C/C++:
Код:
#include <stdio.h>
int pow10mod19(int k)
{
int r = 1;
for(int i = 1; i <= k; i++)
{
r = (r * 10) % 19;
}
return r;
}
int main()
{
for(int x = 0; ; x++)
{
int k = 2 * pow10mod19(x) - 4;
if(k % 19 == 0)
printf("Найдено: %i\n", x);
}
return 0;
}
int pow10mod19(int k)
{
int r = 1;
for(int i = 1; i <= k; i++)
{
r = (r * 10) % 19;
}
return r;
}
int main()
{
for(int x = 0; ; x++)
{
int k = 2 * pow10mod19(x) - 4;
if(k % 19 == 0)
printf("Найдено: %i\n", x);
}
return 0;
}
Цитата: Nixus
То же самое на C/C++:
Код:
#include <stdio.h>
int pow10mod19(int k)
{
int r = 1;
for(int i = 1; i <= k; i++)
{
r = (r * 10) % 19;
}
return r;
}
int main()
{
for(int x = 0; ; x++)
{
int k = 2 * pow10mod19(x) - 4;
if(k % 19 == 0)
printf("Найдено: %i\n", x);
}
return 0;
}
int pow10mod19(int k)
{
int r = 1;
for(int i = 1; i <= k; i++)
{
r = (r * 10) % 19;
}
return r;
}
int main()
{
for(int x = 0; ; x++)
{
int k = 2 * pow10mod19(x) - 4;
if(k % 19 == 0)
printf("Найдено: %i\n", x);
}
return 0;
}
Верно, но IMHO слишком медленно.
Кстати, можно было бы ускорить, применив динамическое программирование.
Цитата: oxotnik333
если можно, уточните:
допустим было 102, после перестановки получается 210 ?
в таком случае в цикле while (float результат_деления!=2)
делается счетчик i++
далее число переводится в строку, подставляем в одну переменную AnsiString "2" вначале а в другую в конце
переводим их StrToInt делим большее на меньшее, смотрим результат
как цикл закончился во 2-й переменной как раз и будет искомое число
допустим было 102, после перестановки получается 210 ?
в таком случае в цикле while (float результат_деления!=2)
делается счетчик i++
далее число переводится в строку, подставляем в одну переменную AnsiString "2" вначале а в другую в конце
переводим их StrToInt делим большее на меньшее, смотрим результат
как цикл закончился во 2-й переменной как раз и будет искомое число
Очень медленный способ.
А если учесть что первое такое число 10526315789473684, ждать решения будешь вечность.
Цитата: Green
IMHO слишком медленно.
Кстати, можно было бы ускорить, применив динамическое программирование.
Кстати, можно было бы ускорить, применив динамическое программирование.
Ну я и не стремился к оптимизации. :-) Можно, конечно, вычисление pow10mod19 сделать в главном цикле, но тогда запутаньнее будет. Я стремился к ясности кода в данном случае. Хотя тормозов тоже не заметил.
ЗЫ. Более быстрое решение, по-моему, невозможно.
Код:
int64 num = 2;
int degree = 1;
while (num *10 + 2 != 2 * exp(ln(10)*degree)+num)
{
num = exp(ln(2) * (degree+1)) * exp(ln(10)*degree) + num;
++degree;
};
int degree = 1;
while (num *10 + 2 != 2 * exp(ln(10)*degree)+num)
{
num = exp(ln(2) * (degree+1)) * exp(ln(10)*degree) + num;
++degree;
};
// еще мона оптимизировать =)
З.Ы. На компе не тестил, думаю должно работать.
Цитата: Nixus
Ну я и не стремился к оптимизации. :-) Можно, конечно, вычисление pow10mod19 сделать в главном цикле, но тогда запутаньнее будет. Я стремился к ясности кода в данном случае. Хотя тормозов тоже не заметил.
ЗЫ. Более быстрое решение, по-моему, невозможно.
ЗЫ. Более быстрое решение, по-моему, невозможно.
Я имел в виду алгоритм, а не реализацию, когда говорил "медленно". Хотя я могу и ошибаться.
В любом случае решение мне нравится.
цикл по i = 0, шаг 10 до ...
вложенный цикл по m=0, шаг 10:
начинать с n = 200*i + 4 + m
таким образом будем бегать по разрядам (2 сотни, 2 тыщи, 20 тыщ... и т.д.), что уменьшает сильно количество итерраций + отсекаем ненужные значения последнего разряда которые при делении не дадут 2
дальше все просто, делим n пополам, сравниваем полученные результаты...
вот примерно так...
завтра в код переведу
вложенный цикл по m=0, шаг 10:
начинать с n = 200*i + 4 + m
таким образом будем бегать по разрядам (2 сотни, 2 тыщи, 20 тыщ... и т.д.), что уменьшает сильно количество итерраций + отсекаем ненужные значения последнего разряда которые при делении не дадут 2
дальше все просто, делим n пополам, сравниваем полученные результаты...
вот примерно так...
завтра в код переведу
хм... немного не додумал с формулами и шагом цикла...
но смысл остается тот же
т.е: внешний цикл задает число 20..(n нулей)..04
при шаге i=1 2*10^i+4
внутрениий пробегает промежуток от 20..(n нулей)..04 до 29..(n девяток)..94 с шагом 10
далее как написано ранее...
но смысл остается тот же
т.е: внешний цикл задает число 20..(n нулей)..04
при шаге i=1 2*10^i+4
внутрениий пробегает промежуток от 20..(n нулей)..04 до 29..(n девяток)..94 с шагом 10
далее как написано ранее...
ой, конечно ж я ошибся в реализации. надо так:
Код:
int64 num = 2;
int degree = 1;
while (num *10 + 2 != 2 * exp(ln(10)*degree)+num)
{
num = (num*20 + 2) mod (exp(ln(10)*(degree+1)));
++degree;
};
int degree = 1;
while (num *10 + 2 != 2 * exp(ln(10)*degree)+num)
{
num = (num*20 + 2) mod (exp(ln(10)*(degree+1)));
++degree;
};
Цитата: Green
Предлагайте решения в виде кода (желательно с описанием алгоритма). Будем выбирать самое оригинальное. Хотя вариантов IMHO мало... :)
Код:
using System;
using System.Text;
namespace ConsoleApplication1 {
class Program {
const int N = 50;
static void Main(string[] args) {
byte[] si = new byte[N]; // si = single - искомое
byte[] du = new byte[N]; // du = double - удвоенное
si[0] = 2;
du[0] = 4; // si[0] * 2
int i = 0;
while (du != 2 || si != 1) {
byte next_si = du;
si[i + 1] = next_si;
byte next_du = (byte) (next_si * 2 + du[i + 1]);
du[i + 1] = (byte)(next_du % 10);
du[i + 2] = (byte)(next_du / 10);
++i;
}
Console.WriteLine("Искомое число: ");
for (int j = i; j >= 0; --j)
Console.Write(si[j]);
Console.WriteLine();
Console.WriteLine("Удвоенное число: ");
for (int j = i; j >= 0; --j)
Console.Write(du[j]);
Console.WriteLine();
Console.ReadLine();
}
}
}
using System.Text;
namespace ConsoleApplication1 {
class Program {
const int N = 50;
static void Main(string[] args) {
byte[] si = new byte[N]; // si = single - искомое
byte[] du = new byte[N]; // du = double - удвоенное
si[0] = 2;
du[0] = 4; // si[0] * 2
int i = 0;
while (du != 2 || si != 1) {
byte next_si = du;
si[i + 1] = next_si;
byte next_du = (byte) (next_si * 2 + du[i + 1]);
du[i + 1] = (byte)(next_du % 10);
du[i + 2] = (byte)(next_du / 10);
++i;
}
Console.WriteLine("Искомое число: ");
for (int j = i; j >= 0; --j)
Console.Write(si[j]);
Console.WriteLine();
Console.WriteLine("Удвоенное число: ");
for (int j = i; j >= 0; --j)
Console.Write(du[j]);
Console.WriteLine();
Console.ReadLine();
}
}
}
Умножение в столбик.
За базу принял 2 и 4 - это последние числа искомого и удвоенного искомого.
Следующее число искомого - это первое число удвоенного, его умножаем на два и получаем следующие числа удвоенного (не забываем о переносе разрядов).
Код:
#include <iostream>
using namespace std;
int main() {
const int len = 1024;
char number[len + 1];
unsigned __int64 x = 2,z;
int i = 0;
while (i < len) {
number='0';
i++;
}
number = 0;
int cpos = len;
char tmp;
do {
cpos--;
z = x;
i = 0;
// Прибавляем к number x*(10^(len-cpos-1))
while (z > 0) {
tmp = number[cpos - i];
tmp += z % 10;
z /= 10;
if (tmp > '9') { // переход на следующий разряд
tmp -= 10;
z++;
}
number[cpos - i] = tmp;
i++;
}
if (number[cpos] == '2') { // Возможно, наше число
char number2[len + 1];
i = 0;
while (i < len) {
number2 = 0;
i++;
}
number2[len]=0;
int pos = len - 1, mem = 0;
// Умножим на 2 для проверки
while (pos > cpos) {
tmp = number2[pos] + (number[pos] - '0') << 1;
if (tmp > 9) { // Перход в следующий разряд
mem = tmp / 10;
tmp = tmp % 10;
}
number2[pos] = tmp;
i = pos;
while (mem != 0) {
i--;
if(i <= cpos) { // Перенос за границы числа(оригинал и произведение должны совпадать по количеству разрядов)
pos = cpos;
break;
}
tmp = number2 + mem;
if (tmp > 9) { // Перход в следующий разряд
mem = tmp / 10;
tmp = tmp % 10;
}
else
mem = 0;
number2 = tmp;
}
pos--;
}
if ((pos == cpos) && (mem == 0))
cout<<&number[cpos + 1]<<endl;
}
x = x << 1; // Умножаем х на 2
} while (x != 0); // Пока х не переполнится
return 0;
}
using namespace std;
int main() {
const int len = 1024;
char number[len + 1];
unsigned __int64 x = 2,z;
int i = 0;
while (i < len) {
number='0';
i++;
}
number = 0;
int cpos = len;
char tmp;
do {
cpos--;
z = x;
i = 0;
// Прибавляем к number x*(10^(len-cpos-1))
while (z > 0) {
tmp = number[cpos - i];
tmp += z % 10;
z /= 10;
if (tmp > '9') { // переход на следующий разряд
tmp -= 10;
z++;
}
number[cpos - i] = tmp;
i++;
}
if (number[cpos] == '2') { // Возможно, наше число
char number2[len + 1];
i = 0;
while (i < len) {
number2 = 0;
i++;
}
number2[len]=0;
int pos = len - 1, mem = 0;
// Умножим на 2 для проверки
while (pos > cpos) {
tmp = number2[pos] + (number[pos] - '0') << 1;
if (tmp > 9) { // Перход в следующий разряд
mem = tmp / 10;
tmp = tmp % 10;
}
number2[pos] = tmp;
i = pos;
while (mem != 0) {
i--;
if(i <= cpos) { // Перенос за границы числа(оригинал и произведение должны совпадать по количеству разрядов)
pos = cpos;
break;
}
tmp = number2 + mem;
if (tmp > 9) { // Перход в следующий разряд
mem = tmp / 10;
tmp = tmp % 10;
}
else
mem = 0;
number2 = tmp;
}
pos--;
}
if ((pos == cpos) && (mem == 0))
cout<<&number[cpos + 1]<<endl;
}
x = x << 1; // Умножаем х на 2
} while (x != 0); // Пока х не переполнится
return 0;
}
Вывод прграммы
Код:
105263157894736842
105263157894736842105263157894736842
105263157894736842105263157894736842105263157894736842
105263157894736842105263157894736842
105263157894736842105263157894736842105263157894736842
Цитата: max_dark
Код:
Вывод прграммы
[code]
105263157894736842
105263157894736842105263157894736842
105263157894736842105263157894736842105263157894736842
[code]
105263157894736842
105263157894736842105263157894736842
105263157894736842105263157894736842105263157894736842
закономерность прослеживается:
105263157894736842105263157894736842105263157894736842105263157894736842 - следующее число
105263157894736842105263157894736842105263157894736842105263157894736842105263157894736842 - следующее
В посте Nixus приведены необходимые математические выкладки.
В итоге ищем степени n:
(10^n -2) mod 19 = 0
Подходят все n = 17 и далее с шагом 18: 17,35,53,71,89,107, ...
Ответ: 20*(10^n - 2)/19 + 2
В итоге ищем степени n:
(10^n -2) mod 19 = 0
Код:
#include<stdio.h>
main()
{
int i,n,ost,del;
clrscr();
del=19;
ost=8;
n=100;
for(i=2;i<n;i++)
{
ost=(ost*10+18)%del;
if(ost==0)
printf("\n\nn=%ld ost=%ld",i,ost);
}
}
main()
{
int i,n,ost,del;
clrscr();
del=19;
ost=8;
n=100;
for(i=2;i<n;i++)
{
ost=(ost*10+18)%del;
if(ost==0)
printf("\n\nn=%ld ost=%ld",i,ost);
}
}
Подходят все n = 17 и далее с шагом 18: 17,35,53,71,89,107, ...
Ответ: 20*(10^n - 2)/19 + 2
Курим теорию чисел.
И. М. Виноградов. Основы теории чисел. Главы 3 и 6. По-моему, задача чисто математическая, решается с помощью вышеупомянутого учебника и ручки с листком бумаги в течении 3-5 минут. Необходимости в программировании тут нет.
С утра на свежую голову подумаю и выложу.
P. S. Гугль "Виноградов основы теории чисел", первая ссылка.
И. М. Виноградов. Основы теории чисел. Главы 3 и 6. По-моему, задача чисто математическая, решается с помощью вышеупомянутого учебника и ручки с листком бумаги в течении 3-5 минут. Необходимости в программировании тут нет.
С утра на свежую голову подумаю и выложу.
P. S. Гугль "Виноградов основы теории чисел", первая ссылка.
Цитата: cheburator
Курим теорию чисел.
И. М. Виноградов. Основы теории чисел. Главы 3 и 6. По-моему, задача чисто математическая, решается с помощью вышеупомянутого учебника и ручки с листком бумаги в течении 3-5 минут. Необходимости в программировании тут нет.
С утра на свежую голову подумаю и выложу.
P. S. Гугль "Виноградов основы теории чисел", первая ссылка.
И. М. Виноградов. Основы теории чисел. Главы 3 и 6. По-моему, задача чисто математическая, решается с помощью вышеупомянутого учебника и ручки с листком бумаги в течении 3-5 минут. Необходимости в программировании тут нет.
С утра на свежую голову подумаю и выложу.
P. S. Гугль "Виноградов основы теории чисел", первая ссылка.
По-моему в топике не спрашивалось, где найти информацию для решения, не спрашивалось, как решить.
В топике говорилось: "Предлагайте решения в виде кода (желательно с описанием алгоритма). Будем выбирать самое оригинальное. Хотя вариантов IMHO мало...".
Пока вариантов определилось два:
1) при помощи уравнения,
2) последовательным нахождением чисел начиная с младшего.
Как уже говорил, IMHO вариантов мало.
Лично я подошел к решению вторым способом. Код специально пока не выкладываю, но он не сильно отличается от уже приведенных.
можна последовательно находить с со старшего разряда, но это существенно алгоритм не меняет...
Цитата: Dart Bobr
можна последовательно находить с со старшего разряда, но это существенно алгоритм не меняет...
С младшего как-то проще. "Умножение в стлолбик" с начальной школы известно. :rolleyes:
Разгадайте и мою шараду :) Работает ессно тоже очень быстро.
Требуется ли построить алгоритм для нахождения всех таких чисел ?
Код:
#include <iostream>
#include <math.h>
using namespace std;
unsigned __int64 found;
unsigned __int64 f( unsigned __int64 i, unsigned __int64 j , unsigned __int64 w)
{
unsigned __int64 found;
while(i < j) {
found = (j+i) / 2;
unsigned __int64 r = (found << 1) - found/ 10 ;
if( (w) == r ) {
if( found % 10 != 2)
{
unsigned __int64 r1 = f( i, found-1,w);
unsigned __int64 r2 = f(found+1,j,w);
if( r1 != 0)
return r1;
else if ( r2 != 0)
return r2;
else return 0;
}
cout<<found;
return found;
}
else if( (w ) < r) {
j = found;
}
else {
i = found+1;
}
}
return 0;
}
unsigned __int64 mpow( unsigned __int64 a, unsigned __int64 b)
{
unsigned __int64 result = a;
for( int i = 0; i < b - 1; i++)
result *= a;
return result;
}
int main()
{
for(int i1 = 1; i1 <= 19; i1++)
{
unsigned __int64 check = mpow(10,i1)* 2;
unsigned __int64 i = 0, j = ( (unsigned __int64)1<<(unsigned __int64)63) - 1;
unsigned __int64 r = f( i, j, check);
if ( r != 0)
return 0;
}
cout<<"No solution"<<endl;
return 0;
}
#include <math.h>
using namespace std;
unsigned __int64 found;
unsigned __int64 f( unsigned __int64 i, unsigned __int64 j , unsigned __int64 w)
{
unsigned __int64 found;
while(i < j) {
found = (j+i) / 2;
unsigned __int64 r = (found << 1) - found/ 10 ;
if( (w) == r ) {
if( found % 10 != 2)
{
unsigned __int64 r1 = f( i, found-1,w);
unsigned __int64 r2 = f(found+1,j,w);
if( r1 != 0)
return r1;
else if ( r2 != 0)
return r2;
else return 0;
}
cout<<found;
return found;
}
else if( (w ) < r) {
j = found;
}
else {
i = found+1;
}
}
return 0;
}
unsigned __int64 mpow( unsigned __int64 a, unsigned __int64 b)
{
unsigned __int64 result = a;
for( int i = 0; i < b - 1; i++)
result *= a;
return result;
}
int main()
{
for(int i1 = 1; i1 <= 19; i1++)
{
unsigned __int64 check = mpow(10,i1)* 2;
unsigned __int64 i = 0, j = ( (unsigned __int64)1<<(unsigned __int64)63) - 1;
unsigned __int64 r = f( i, j, check);
if ( r != 0)
return 0;
}
cout<<"No solution"<<endl;
return 0;
}
Требуется ли построить алгоритм для нахождения всех таких чисел ?
Цитата: Green
Предлагайте решения в виде кода (желательно с описанием алгоритма).
Код:
#include <iostream>
void main ()
{
const std::string s1 ("105263157894736842");
std::string s2 (s1);
while (true)
{
std::cout << s2;
s2 += s1;
}
// Пока хватает памяти для s2...
}
void main ()
{
const std::string s1 ("105263157894736842");
std::string s2 (s1);
while (true)
{
std::cout << s2;
s2 += s1;
}
// Пока хватает памяти для s2...
}
Цитата: cheburator
Код:
Пока хватает памяти для s2...
можно сэкономить на памяти - не хранить вообще эту строку (в задаче про хранение вроде ничего небыло), просто на консоль шлепать циклами, пока не позеленеешь ;)
Цитата: cheburator
Код:
#include <iostream>
void main ()
{
const std::string s1 ("105263157894736842");
std::string s2 (s1);
while (true)
{
std::cout << s2;
s2 += s1;
}
// Пока хватает памяти для s2...
}
void main ()
{
const std::string s1 ("105263157894736842");
std::string s2 (s1);
while (true)
{
std::cout << s2;
s2 += s1;
}
// Пока хватает памяти для s2...
}
Да... вижу, Виноградов тебе очень помог... :D
vAC, этот же "алгоритм" можно применить и для ОБПФ (Очень Быстрого ПФ) ? :D
P.S. Предлагалось привести код решения задачи, а не код лишь вывода результата. Но, как говориться, от каждого по способностям. "Решение" принято. Думаю, на утешительный приз потянет.
Цитата: hardcase
С младшего как-то проще. "Умножение в стлолбик" с начальной школы известно. :rolleyes:
Да деление вроди как следующая тема после умножения.. :rolleyes: =) Но, все-равно это один и тот же алгоритм )
Цитата: Green
vAC, этот же "алгоритм" можно применить и для ОБПФ (Очень Быстрого ПФ) ? :D
P.S. Предлагалось привести код решения задачи, а не код лишь вывода результата. Но, как говориться, от каждого по способностям. "Решение" принято. Думаю, на утешительный приз потянет.
P.S. Предлагалось привести код решения задачи, а не код лишь вывода результата. Но, как говориться, от каждого по способностям. "Решение" принято. Думаю, на утешительный приз потянет.
Да, Green, вы меня разоблачили, это так и есть, только зачем же надо было раскрывать мой секрет во всеуслышанье? :)
Подождите, кажется задание звучало так:
Цитата: Green
Простенькая задачка: есть число, которое заканчивается на 2, если переставить 2-ку в начало этого числа - то получится число в два раза большее, найти исходное число.
Предлагайте решения в виде кода (желательно с описанием алгоритма). Будем выбирать самое оригинальное. Хотя вариантов IMHO мало... :)
Призы, как обычно,- зелененькие квадратики... :)
Предлагайте решения в виде кода (желательно с описанием алгоритма). Будем выбирать самое оригинальное. Хотя вариантов IMHO мало... :)
Призы, как обычно,- зелененькие квадратики... :)
Не код решения задачи, а решение в виде кода - это две совершенно разные фразы, Green.
В первом случае решение подразумевает сам процесс получения результата.
Во-втором подразумевается сам результат.
Поэтому считаю, что решение от cheburator вполне удовлетворяет условиям, сформулированным в первом посте и заслуживает первого места.
Недолго глядя на вашу задачу,Green, позволю себе нарушить ваше требование относительно кода (за нехваткой времени) и приведу свой алгоритм в словесно-числовом формате.
Виноградова читать для такой простой задачи не надо - это как кувалдой по мухе. Достаточно вспомнить те времена, когда нас учили делить столбиком (причем на 2) и умножать (также на 2).
Итак:
Число заканчивается цифрой 2. Если ее переставить, то получим в два раза бОльшее. Отсюда, а также из того что число цифр в числах одинаково, следует что это число и число, умноженное на два, представимо в виде:
***********2
2**********4
Можно конечно сразу вписать дополнительные цифры.
Теперь просто делим второе на 2, получаем 1********2, записываем его в первую строку,а также, зная что цифры в середине одинаковые у обоих чисел, то записываем эту единицу после 2 во втором:
1**********2
21*********4
еще раз делим второе на 2, получаем 10*******2. Поступаем аналогично:
10*********2
210********4
105********2
2105*******4
1052*******2
21052******4
10526******2
210526*****4
И до тех пор, пока под двойкой не окажется 4.
Виноградова читать для такой простой задачи не надо - это как кувалдой по мухе. Достаточно вспомнить те времена, когда нас учили делить столбиком (причем на 2) и умножать (также на 2).
Итак:
Число заканчивается цифрой 2. Если ее переставить, то получим в два раза бОльшее. Отсюда, а также из того что число цифр в числах одинаково, следует что это число и число, умноженное на два, представимо в виде:
***********2
2**********4
Можно конечно сразу вписать дополнительные цифры.
Теперь просто делим второе на 2, получаем 1********2, записываем его в первую строку,а также, зная что цифры в середине одинаковые у обоих чисел, то записываем эту единицу после 2 во втором:
1**********2
21*********4
еще раз делим второе на 2, получаем 10*******2. Поступаем аналогично:
10*********2
210********4
105********2
2105*******4
1052*******2
21052******4
10526******2
210526*****4
И до тех пор, пока под двойкой не окажется 4.
Цитата: vAC
...приведу свой алгоритм в словесно-числовом формате...
Прошу прощения, просто бегло пробежался по теме, но доп. формулировка с пояснением не помешает :) На приз я не претендую ;)
P.S. Если рассматривать сам процесс решения, то думаю что это будет самым красивым и простым алгоритмом.
P.P.S. Кстати, Green, вы призы будете давать за лучший алгоритм или лучшую реализацию лучшего алгоритма?
P.S. Если рассматривать сам процесс решения, то думаю что это будет самым красивым и простым алгоритмом.
P.P.S. Кстати, Green, вы призы будете давать за лучший алгоритм или лучшую реализацию лучшего алгоритма?
Ну приз здесь возможен только один - "приз зрительских симпатий", поэтому даю его не я а все присутствующие. Так что им и решать, за что конкретно. :)
А утешительные? В виде половинки квадратика :)
Нет, утешильный приз сегодня поднятие репутации на 10000000 очков, вывешивание фотографии на первую страничку форума и бегущая строка с именем, а также диферамбы. Извините за сарказм, конечно, но, задам вам вопрос, вы в данной теме писали только из-за приза??
Цитата: Green
Простенькая задачка: есть число, которое заканчивается на 2, если переставить 2-ку в начало этого числа - то получится число в два раза большее, найти исходное число.
Предлагайте решения в виде кода (желательно с описанием алгоритма). Будем выбирать самое оригинальное. Хотя вариантов IMHO мало... :)
Призы, как обычно,- зелененькие квадратики... :)
Предлагайте решения в виде кода (желательно с описанием алгоритма). Будем выбирать самое оригинальное. Хотя вариантов IMHO мало... :)
Призы, как обычно,- зелененькие квадратики... :)
Исходные данные:
Первое число: [1][X1][X2]...[Xn][2]
Второе число: [2][1][X1][X2]...[Xn]
Первое число в 2 раза меньше второго.
Таким образом, [Xn-1] = 2 * [Xn]
Теперь пример на MFC, поиска первого такого числа:
Код:
CString strRes = "2";
int nInteger = 0, nRemainder = 2;
int nProduct = 0;
do
{
nProduct = nRemainder * 2 + nInteger;
nInteger = nProduct / 10;
nRemainder = nProduct % 10;
strRes.Format(strRes + "%d", nRemainder);
}
while(nProduct != 10);
strRes.Format(strRes + "%d", nInteger);
strRes.MakeReverse();
MessageBox(strRes);
int nInteger = 0, nRemainder = 2;
int nProduct = 0;
do
{
nProduct = nRemainder * 2 + nInteger;
nInteger = nProduct / 10;
nRemainder = nProduct % 10;
strRes.Format(strRes + "%d", nRemainder);
}
while(nProduct != 10);
strRes.Format(strRes + "%d", nInteger);
strRes.MakeReverse();
MessageBox(strRes);
Цитата: vAC
...считаю, что решение от cheburator вполне удовлетворяет условиям, сформулированным в первом посте и заслуживает первого места.
:) Я может место и заслуживаю, но, имхо, сама задача ничего не заслуживает как задача по программированию :) Это - чисто математическая задача.
Green, без обид, это всего лишь мое личное мнение.
P. S. Повысим репутацию Виноградова и vAC (за решение без теории чисел)
Цитата: Dart Bobr
Нет, утешильный приз сегодня поднятие репутации на 10000000 очков, вывешивание фотографии на первую страничку форума и бегущая строка с именем, а также диферамбы. Извините за сарказм, конечно, но, задам вам вопрос, вы в данной теме писали только из-за приза??
Я же писал, что на приз не претендую - значит не претендую, не берите пример с меня, читайте тему полностью :). Я за других беспокоюсь :)
Цитата: cheburator
:) Я может место и заслуживаю, но, имхо, сама задача ничего не заслуживает как задача по программированию :) Это - чисто математическая задача.
Green, без обид, это всего лишь мое личное мнение.
Green, без обид, это всего лишь мое личное мнение.
Ну вот, тему пропустил, решение уже есть, позвольте хоть мнение выскажу.
Всетаки если можно задачу решить с помощю ветвления - то уже программисткая. Мне нравится, хотя и простенькая.
А вот тут совсем уж программисткое решение еще одной интересной задачи.
Green пиши есче.
Извините за некропостинг - тема интересная.
Вообще, решения от Nixus и hardcase трудно переплюнуть, но я попытался хотя бы придумать альтернативный алгоритм, который не будет искать результат вечность. В общем-то это доведенный до ума алгоритм от oxotnik333.
Итак, исследование
20 > 02 * 2, 21 < 12 * 2, и далее все сравнения дают меньше — можно не анализировать
210 > 102 * 2, 211 < 112*2, и далее все сравнения дают меньше — можно не анализировать
...
то есть для каждой степени десятки достаточно найти число k, которому будет удовлетворять условие
2* first(k) < second(k) && 2 * first(k + 1) >= second(k + 1)
и можно переходить к следующей степени или заканчивать поиск. В формуле first(), second() - функции, находящие первое и второе число, k = 10^n + i, где i < 9 * 10^(n).
Поиск можно вести известным старым способом — прибавляя или отнимая половину шага, начальное значение которого равно половине диапазона, в котором ведется поиск.
Реализация немного корявая (только алгоритм проверял, без приведения в нормальный вид), но рабочая.
То есть, можно решить почти тупо в лоб, но не ждать результата вечность.
Вообще, решения от Nixus и hardcase трудно переплюнуть, но я попытался хотя бы придумать альтернативный алгоритм, который не будет искать результат вечность. В общем-то это доведенный до ума алгоритм от oxotnik333.
Итак, исследование
20 > 02 * 2, 21 < 12 * 2, и далее все сравнения дают меньше — можно не анализировать
210 > 102 * 2, 211 < 112*2, и далее все сравнения дают меньше — можно не анализировать
...
то есть для каждой степени десятки достаточно найти число k, которому будет удовлетворять условие
2* first(k) < second(k) && 2 * first(k + 1) >= second(k + 1)
и можно переходить к следующей степени или заканчивать поиск. В формуле first(), second() - функции, находящие первое и второе число, k = 10^n + i, где i < 9 * 10^(n).
Поиск можно вести известным старым способом — прибавляя или отнимая половину шага, начальное значение которого равно половине диапазона, в котором ведется поиск.
Реализация немного корявая (только алгоритм проверял, без приведения в нормальный вид), но рабочая.
Код:
#include <iostream>
//typedef unsigned long long uint64_t;
uint64_t intPow10(int n)
{
uint64_t result = 1;
for(int i = 0; i < n; ++i) result *= 10;
return result;
}
uint64_t first2(uint64_t k)
{
return k * 10 * 2 + 2 * 2; // умноженное на 2
}
uint64_t second(uint64_t k, int n)
{
return k + 2 * intPow10(n + 1);
}
uint64_t findK(int n)
{
uint64_t i = (9 * intPow10(n)) >> 1;
uint64_t di = i >> 1;
uint64_t k = 0;
uint64_t iMore = 0;
while(true)
{
k = intPow10(n) + i;
uint64_t s1 = second(k, n);
uint64_t s2 = second(k + 1, n);
uint64_t f1 = first2(k);
uint64_t f2 = first2(k + 1);
if((f1 < s1) && (f2 >= s2)) break;
else if(f1 > s1)
{
i -= di;
}
else if(f1 < s1)
{
i += di;
}
else return k;
di = di >> 1;
if(!di) di = 1;
}
if(first2(k + 1) == second(k + 1, n))
return k + 1;
else
return 0;
}
int main()
{
uint64_t k = 0;
int n = 0;
while (true)
{
k = findK(n);
if (k) break;
++n;
}
std::cout << k << std::endl;
return 0;
}
//typedef unsigned long long uint64_t;
uint64_t intPow10(int n)
{
uint64_t result = 1;
for(int i = 0; i < n; ++i) result *= 10;
return result;
}
uint64_t first2(uint64_t k)
{
return k * 10 * 2 + 2 * 2; // умноженное на 2
}
uint64_t second(uint64_t k, int n)
{
return k + 2 * intPow10(n + 1);
}
uint64_t findK(int n)
{
uint64_t i = (9 * intPow10(n)) >> 1;
uint64_t di = i >> 1;
uint64_t k = 0;
uint64_t iMore = 0;
while(true)
{
k = intPow10(n) + i;
uint64_t s1 = second(k, n);
uint64_t s2 = second(k + 1, n);
uint64_t f1 = first2(k);
uint64_t f2 = first2(k + 1);
if((f1 < s1) && (f2 >= s2)) break;
else if(f1 > s1)
{
i -= di;
}
else if(f1 < s1)
{
i += di;
}
else return k;
di = di >> 1;
if(!di) di = 1;
}
if(first2(k + 1) == second(k + 1, n))
return k + 1;
else
return 0;
}
int main()
{
uint64_t k = 0;
int n = 0;
while (true)
{
k = findK(n);
if (k) break;
++n;
}
std::cout << k << std::endl;
return 0;
}
То есть, можно решить почти тупо в лоб, но не ждать результата вечность.