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

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

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

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

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

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

0
kolioi avatar kolioi 641 Точки

Ето и кратко доказателство, че 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 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
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.