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
MartinBG avatar MartinBG 4803 Точки

Тази задача не ми излизаше от главата, откакто я видях тук, а след като си купих и книгата, намирането на решението ѝ ми се превърна в нещо като фикс идея.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 13 Точки

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 4803 Точки

@vlad.dinev

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

 

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

 

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

 

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

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

 

Поздрави!

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

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

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

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

Поздрави!

0
MartinBG avatar MartinBG 4803 Точки

Пробвах двете версии и на настолното си PC (i5, 2.6-3.2GHz) и твоята е по-бърза с около 1 секунда (7.1 vs 8.1s) или около 15%, както се очакваше.

Поздрави!

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

@MartinBG такаа, пробвах твоя и моя код копирани от тук и получих следното:

 

64bit Dual Core Intel Pentium 2117U @ 1.8GHz:

MinGW GCC 5.3.0 - 16.6 s и 10.5 s

TDM GCC 5.1.0

64 битов код - 13.2 и 12.1

32 битов код - 12.8 и 11.9

 

64bit Quad Core ARMv8 @ 1.2GHz:

GCC 4.2.9 - 34.4 s и 32.5 s

 

Разликите варират доста, особено при първия тест. C++ кода така написан се предполага да е по-бавен, но чак пък с 1/3 по-бавен е странно. Помислих, че може да е заради линкването, TDM линква статично по default, та пробвах да линкна статично и динамично с TDM и с MinGW, но осезаема разлика нямаше. 

Изводът е, че кодът е важен, но компилаторa повече. Ама недей леж' на тая кълка :)

1
08/05/2017 05:22:06
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.