• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Ridicarea la putere in timp logaritmic

2
  • Publicat de Andrei Avădănei
  • în C/C++ · Tehnic
  • — 19 nov., 2009 at 9:05 pm

Probabil au fost cateva persoane ce nu au inteles la un moment dat rezolvarea problemei Ucif in O(1) explicata de Alex si Andrei Misarca si au dorit sa inteleaga ce a facut Cosmina in prezentarea problemei.Astfel noi vom incerca sa ne jucam cu problema de mai sus dar folosind o metoda de rezolvare nu tocmai optima in cazul problemei respective , ci doar o vom folosi pentru a avea un exemplu pe care sa ne bazam.

Ne vom axa doar pe determinarea ultimei cifrei a lui x^x.Metoda clasica de rezolvare presupune ridicarea la putere in timp liniar.:


int ucif(int x,int n,int modul)
{
    if(n==0) return 1;
    int cif = 1;
    while(n--)
    {
        cif = (cif*x)%modul; 
    }
    return cif;
}
// Modalitate de apelare:
printf("%d",ucif(9,9,10));

Din fericire,aceasta solutie va obtine punctajul maxim daca nu ma insel pe testele la problema respectiva,insa cu marirea lui n se va simti o diferenta enorma in timpul de executie, datorita complexitatii acestuia(n^2).
Pentru asta va trebui sa ne folosim de ridicarea in timp logaritmic, o rezolvare ce va imbunatati mult timpul de executie al algoritmului.

int ucif(int x,int n,int modul)
{
	int cif = 1;
	int a;
	if(n==0) return 1;
	
	a = x;
    for (int i = 0; (1<<i ) < = n; i++)  // Luam toti biti lui p la rand
    {
        if ( ((1<<i) & n) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
            cif= (cif * a) % modul;
     
           a=(a * a) % modul; // Inmultim a cu a ca sa obtinem n^(2^(i+1))
   }
    return cif;
}
// Modalitate de apelare:
printf("%d",ucif(9,9,10));

In cazul in care doriti o rezolvare recursiva , puteti alege rezolvarea Cosminei de la problema Ucif , cu cateva modificari sa o facem in stilul celor de mai sus(cea de mai jos) :

int ucif(int x, int n,int modul)   
{   
    int tip;
    if(n==0) return 1;   
    if(n%2==1) return (x*ucif(x,n-1,modul))%modul;   
    tip=ucif(x,n/2,modul)%modul;   
    return tip*tip%modul;   
}  

Puteti citi mai multe detalii de fundamentul matematic al acestui algoritm pe wikipedia.

Etichete: algoritmiC++informaticalogaritmareOlimpiadaridicarea la putereridicarea la putere in timp logaritmictutorialeucif

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Google Swirl – dinamizeaza cautarile imaginilor cu noua aplicatie de la Google
  • Articolul următor Google si Microsoft deschid piata windows-ului online – Chrome OS vs Azure

2 Comentarii

  1. challenge spune:
    noiembrie 25, 2009 la 3:53 pm

    „daca vom mari limitele lui n, sa spunem cateva zeci de mii, atunci timpul liniar va duce la o solutie in timp patratic ceea ce este groaznic.” …
    Cum adica pt n foarte mare complexitatea devine din O(n) in O(n^2) ? Mi se pare o aberatie fraza asta, complexitatea unui algoritm este acceasi pentru orice n… ori e O(n) ori O(n^2) … nu pot sa fie ambele in acelasi timp >.<

  2. Avadanei Andrei spune:
    noiembrie 25, 2009 la 4:12 pm

    Imi cer scuze pentru ambiguitate,am reformulat acea fraza.Ideea era ca la un n suficient de mic este insesizabila acel ordin n^2.Cu cat se apropie de n=1000 si il depaseste cu atat impactul asupra timpului este mai criminal. 😀


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • mai 2022
    L Ma Mi J V S D
     1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Ridicarea la putere in timp logaritmic
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons