Софтуерно Инженерство
Loading...
+ Нов въпрос
agogo avatar agogo 12 Точки

Задача 1.181 / Програмиране++=Алгоритми

Здравейте!

Вместо да ходя на море :) се опитвам да реша следната задача:

1.181: Да се намери минималното n, за което първите девет цифри на числото 2 на степен n са 123454321.

Ето моя код: http://fdos.free.bg/sklad/1_181.c

Ето резултати от изпълнение:

при първи цифри:

123 ( n = 90 ) < 1s
1234 ( n = 1545 ) < 1s
12345 ( n = 34555 ) ~ 2s
123454 ( n = 176109 ) ~ 10s
1234543 ( n = 176109 ) ~ 10s

12345432 - изпълнява се повече от 50 мин и продължава.

 

Искам да попитам има ли по-рационално решение от това, което използвам като алгоритъм?

И дали сте решавали тази задачи и какъв резултат сте получили

Благодаря, предварително!

0
C Programming
dimitur_botev avatar dimitur_botev 112 Точки
Best Answer

Интересна задача. Имам една идея, но немога да я разпиша вмомента и не знам дали ще сработи.Но в общи ли ако Number = 2^n, за да решиш задачата ти трябват само първите 9 цифри на Number и ако направиш следното Number = Number / 10^Number.lenght(броят цифри) - 9, би трябвало да получиш резултат от целочислено деление което ще е винаги 9 цифри, тези които ти трябват и после само ги проверяваш дали са рави на 123454321.

Това горе е нещо като псевдо код, понеже C не ми е силен ама би трябвало логиката да е универсална. Дано да съм бил полезен 

EDIT. Също така за да увеличиш бързината запазавай последната стойност на Number и на всяка следваща итерация Number  *=2 Така няма върти цикъл от началото.

0
19/08/2016 21:03:02
agogo avatar agogo 12 Точки

Благодаря!

Много полезен съвет, но в този случай не мога да го използвам защото при намиране на първи цифри 1234543, n = 176109, което е число от 53014 цифри.Това число не се побира в който и да е тип за С, затова използвам масив.

Може би тази задача има решение, може би е "мотичка", която авторите са поставили за забавление, но най-вероятно нямам достатъчно изчислителна мощ на компютъра и търпение:(  Последния тест, който направих бе до n = 1005000, но решение не бе намерено. Оставих компютъра да работи цяла нощ, за да превърти всички n!

Програмата може да се оптимизира, като 123454321 се постави в масив и се сравняват последните 9 елемента. Ако някой е получил решението моля, да го сподели!

Поздрави!

 

 

0
MartinBG avatar MartinBG 791 Точки

Интересна задача!

Нямам решение на проблема, но намерих това:

http://mathforum.org/library/drmath/view/51509.html

"2^70279608 has as its first nine digits 123454321."

Със сигурност има някой по-хитър алгоритъм, от това да въртиш милиони итерации :)

0
kolioi avatar kolioi 394 Точки

Ето и кратко доказателство, че 70,279,608 наистина е решение, т.е. 2^70279608 започва с цифрите 123454321.

Първо изчисляваме 70279608 log 2 = 21,156,270.091506298118993045735591.... Тогава 10^0.091506298118993045735591 = 1.2345432183309575226143399297209... т.е. 2^70279608 наистина започва с цифрите 123454321.

Този метод се използва за да се изчислят началните цифри на много големи числа, които не могат да се поберат в компютър. Например 123^456789 започва с цифрите 4633928101.... Неудобство на метода е това, че следващите цифри са неточни заради натрупване на грешки от закръгляването.

Иначе не се сещам за по-добър алгоритъм. Обаче предложената програма може да се направи малко по-бърза.

Използвам темата, за да кажа две думи за подобна, но по-лесна задача - за това как се изчислява на колко нули завършва n! (имаше някъде в упражненията такава задача). Броя на нулите е равен на степента на 5 в каноничното разлагане на n! и не е необходимо да изчисляваме колко е n! (това се учи в 5-ти клас, доколкото си спомням). Код на C#

            int n = int.Parse(Console.ReadLine()),
                numZeroes = 0;

            for (int i = 5; i <= n; i *= 5)
                numZeroes += n / i;

            Console.WriteLine(numZeroes);

Бързо и лесно, особено за големи стойности на n. Не съм го тествал в Джаджа, но съм сигурен, че работи.

1
19/11/2017 11:56:14
MartinBG avatar MartinBG 791 Точки

Тази задача не ми излизаше от главата, откакто я видях тук, а след като си купих и книгата, намирането на решението ѝ ми се превърна в нещо като фикс идея.laugh

 

Снощи "изтръбуших" интернета в търсене на интелигентно решение и попаднах на още няколко места, където се обсъжда този казус, но никъде нямаше готов алгоритъм за решаването му.

 

В крайна сметка се наложи да си припомня математиката и да използвам нещата, които вече бях открил като подсказки по задачата, а именно:

1. Задачта има решение (70279608 ) - линк, линк2, линк3, линк4

2. От линковете в т.1 и от коментара на kolioi става ясно как се проверява това решение:

70279608 * log 2 = 21156270.091506298118993045735591

10 ^ 0.091506298118993045735591 = 1.234543218330957522614340958985

Остана ми само да тръгна по обратния ред и стигнах до това решение на C++, което успява да намери резултата за под 20 секунди на моята машина (i5 2.3GHz):

#include<iostream>
#include<cmath>
#include<climits>

int main()
{
    const double log_2 = 0.30102999566398119521373889472449;

    double intpart;

    for(int i = 0; i < INT_MAX; i++)
    {
        if (123454321 == int(pow(10.0, modf(i * log_2, &intpart)) * 100000000.0))
        {
            std::cout << "Found it = " << i << std::endl;
            break;
        }
    }

    return 0;
}
Found it = 70279608

Process returned 0 (0x0)   execution time : 11.737 s
Press any key to continue.

 

Сметките в решението със сигурност може да се оптимизират и сигурно ще го направя, но реших първо да го споделя, в случай ,че още някой си губи съня от тази задача. wink

 

Поздрави!

0
07/05/2017 12:53:23
vlad.dinev avatar vlad.dinev 16 Точки

MartinBG, я пробвай това

#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <time.h>

#pragma GCC optimize("O3")

#define GOAL  123454321
#define TOINT 100000000.0

int main(void)
{
	int i;
	double d;
	register const double LOG2 = 0.30102999566398119521373889472449;

	clock_t begin = clock();
    for(i = 0; i <= INT_MAX; i++)
	{
		d = i * LOG2;
		if (GOAL == (int)(pow(10.0, d - (int)d) * TOINT))
			break;
	}
	clock_t end = clock();
	
	printf("%d\n", i);
	printf("Time: %.2f sec\n", (double)(end - begin) / CLOCKS_PER_SEC);

    return 0;
}

и сподели колко ти изкарва. 

Алгоритъмът, който ползваш, изглежда да е най-ефективният познат (така пише в нета :)

Като микро оптимизации съм махнал modf() и константата съм я дефинирал като register. Това подсказва на компилатора да държи стойността в някой от регистрите, с което обаче може и да не се съобрази. Викането на функция в цикъл винаги бави (особено, ако ще се вика 70 милиона пъти), така че е хубаво да се елиминира до колкото може. O3 флага сваля към 0.01% от времето (поне при мен).

На i5 3.2GHz най-бързо се сметна за 5.39s

Поздрави!

1
07/05/2017 23:20:10
MartinBG avatar MartinBG 791 Точки

@vlad.dinev

Благодаря за включването в темата! :)

 

Замяната на modf() с "d - (int)d" е добра идея! Не знам как съм пропуснал да го направя, при условие, че знам за този метод и съм го използвал многократно. blush

 

Не знаех за register директивата при декларирането на променливи - пак научих нещо ново!  :)

 

Въпреки оптимизациите, обаче, времето за изпълнение на двете програми на моя лаптоп е горе-долу еднакво  - около 15 секунди.

Това най-вероятно е заради спецификите на лаптопа и Power management-a му. На "нормална" система твоята версия на програмата би следвало да се представи по-добре от моята.

 

Поздрави!

0
vlad.dinev avatar vlad.dinev 16 Точки

@MartinBG моля, пак заповядай. До сега не се бях сблъсквал с тази задача, научих нещо ново.

При мен разликата между твоята и моята версия е към 1.5s

Ще я пробвам после и на по-слаба машина и ще споделя, че ми стана интересно.

Поздрави!

0