Algorytm konkursowy

Tak samo sobie pomyślałem - 0 na koniec i dodać n. Nawet przerobiłem swoje zadanie ze spoja co nieco... Problem jest taki, że nie specjalnie będzie można wtedy wpleść szybkie potęgowanie.... Oto co mi wyszło - przeproste i przewolne.

#include <iostream>
#include <string>
using namespace std;
int main()
{

	bool czydodac;
	char p;
	string s,s1="11",s2;
	unsigned long long int t, i;
	cin>>t;
	t--;
	while(t--)
	{


		s2=s1;
		s1=s1+'0';

		czydodac=false;
		for(i=s1.size()-1;i>=s1.size()-s2.size();i--)
		{
			if (czydodac==true) {s1[i]++;czydodac=false;}
			p=s1[i]+s2[i-s1.size()+s2.size()]-48;
			if (p>'9') {p-=10;czydodac=true;}
			s1[i]=p;
		}
		if (czydodac==true) s1="1"+s1;
	}
	cout<<s1<<endl;
	cin.get();
	return(0);
}

pomysł świetny :) tyle, że ...
bez Karatsuby, Fouriera nic nie wyjdzie (znaczy wyjdzie, ale nic ważnego)
to daje nam GMP, chyba, że, chyba że ktoś zauważył coś co nam umknęło...

No.. przemyślałem sprawę, wziąłem do serca rady Xitami'ego i oto jakiego potworka stworzyłem:

#include <stdio.h>
#include <conio.h>
#include <math.h>

int main(){
        unsigned int liczba[480000];
        const int N=480000;
        const Z=100000000;
        int przenosze=0,reszta=0,i=0,j=0,potega=0,a=0,licznik=0,x=0;

        for(i=0;i<N;i++){
                liczba[i]=0;}
        printf("Witaj! Program policzy ilosc jedynek w dowolnej potedze liczby 11 !\n\nPodaj potege: ");
        scanf("%d",&potega);
        liczba[0]=1;
        for(i=0;i<potega;i++){
                for(j=0;j<=i;j++){
                        liczba[j]=liczba[j]*11;}
                        for(j=0;j<=i;j++){
                                if(liczba[j]>Z){
                                        przenosze=liczba[j]/Z;
                                        reszta=liczba[j]%Z;
                                        liczba[j+1]=liczba[j+1]+przenosze;
                                        liczba[j]=reszta;}}}
                for(i=0;i<=N;i++){
                        x=Z;
                        for(j=8;j>=0;j--){
                                a=liczba[i]/x;
                                liczba[i]=liczba[i]%x;
                                if(a==1) licznik++;
                        x=x/10;}}
        printf("W %d potedze liczby 11 jest %d jedynek",potega,licznik);
        _getch();
}

 

uwaga pierwsza: znacznie fajniej jest zamiast wielokrotnie powtarzać 480000 napisać
const int N 48000; // albo
"#"define N 480000
różnica nie jest dla mnie do końca jasna, nie byłem kompilatorem to nie wiem, ale dzięki temu tylko w jednym miejscu musimy się tłumaczyć czemu to właśnie tyle
a czemu tyle?

uwaga druga: zauważ, że na początku "liczby" są małe i zaiwaniać z pętelką aż tak daleko jest bez sensu, mnożysz hektary zer!

i kolejna: kolejne magiczne 1000000000 policzyłeś te zera? wszędzie tyle ich samo?
ładniej byłoby napisać np
"#"define RADIX 100000000
uwagi j.w.

dla kolejnych potęg widzę dwie pętle for(), jedna w drugiej, a nawet to samo dwa razy!
wiesz, nawet nie starając się odgadnąć intencji autora wiem, że coś jest nie tak

mam liczbę (liczba[]), "x" razy muszę pomnożyć ją przez jedenaście, idę o zakład, że tylko raz w każdym z X kroków muszę odwiedzić jej kolejne cyfry.
Tak z grubsza, to będzie różnica między 114 lat a wielokrotność czasu istnienia wszechświata :-)

Dziękuję za pomoc, z programem sobie już poradziłem.
Szczególne podziękowania dla Xitami'ego.

Pozdrawiam

Czekajcie, mam w telefonie za mały wyświetlacz, żeby to ogarnąć, czy chłopak zrobił to zadanie zwykłym mnożeniem jedenastek, nawet nie szybkim potęgowaniem?!?

młody jest i nie boi się czekać 114 lat :-)
ma ktoś pod ręką GMP Lib?
ciekawym co powie na mpz_ui_pow_ui (wynik, 11, 2147000000)

Te 114 lat to tak pi razy drzwi, moze moje prawnuki sie dowiedzą jaki jest wynik działania tego programu :)

Byłem ciekaw jak sprawę poprawi szybkie potęgowanie
pisałem je tak by zapotrzebowanie na pamięć nie przekroczyło 2 X wynik

11 ^ 1'000'000 =
000000484348796603303484786492117176320313430499285088952841377983272364419533504 ...
051540601767795728152927732305998507662430620974595565462379530888550684460000001 (1'041'399 cyfr)
104'499 jedynek, 3'661'797'061 mnożeń
Process returned 0 (0x0)   execution time : 217.234 s

czyli 2 minuty 37 sekund

Sprawdziłem ile wykonywanych jest mnożeń pojedynczej precyzji
obliczając 11 ^ 100'000 naiwnym potęgowaniem było 72'319'402, szybkim 67'730'176
teraz obliczenia trwały 1.86 zamiast 9.84 sek.
minimalne zmniejszenie liczby mnożeń nie tłumaczy przyśpieszenia
też liczę przy podstawie miliard, ale mnożenie "wielka" * "wielka" zrobiłem wydaj mnie mi się dość dowcipnie

w szybkim potęgowaniu potrzebne jest podnoszenie do kwadratu,
wyniki podałem przed napisaniem "kwadratowienia", a da się w nim urwać prawie połowę roboty

program dalej samodzielny, ale dramatycznie mi się rozrósł, ma 70 linijek.

wydaje mi się, że OP ma szansę doczekać się wyniku dla 11 ^ 2'000'000'000
może na emeryturze, ale zawsze :-)

---- [ edit ] ---------------------------------------------------
dodałem kwadratowienie, program urósł do 90 linijek,
11 ^ 100'000 - liczba mnożeń 48'565'162, czas 1.48 sek.
11 ^ 200'000 czas 5.59 s
11 ^ 300'000 czas 9.14 s
11 ^ 400'000 czas 21.84 s
11 ^ 1'000'000 czas 165.58 s
11 ^ 2'000'000'000 czas 25 lat
Ideone w prawie 5 sek. potrafi policzyć jedynki w 11 ^ 365'000