Przejdź do głównej zawartości

Rekurencyjny algorytm szybkiego potęgowania O(log n)

/* 
 Title: Rekurencyjny algorytm szybkiego potęgowania o złożoności O(log n) 
*/

#include <stdio.h>

int potegowanie(int podstawa, int wykladnik);

int main()
{
 int wynik = potegowanie( 2, 6 ); /* 2^6 */
 printf( "Wynik potegowania 2^6: %i\n", wynik ); /* Wynik 64 */
 return 0;
}

int potegowanie( int podstawa, int wykladnik )
{
 if( wykladnik == 0 ) /* Potęgowanie podstawy o wykładniku równym 0 */
 {
  return 1;
 }
 else if( wykladnik % 2 == 1 ) /* Dla wykładnika nieparzystego */
 {
  return podstawa * potegowanie( podstawa , wykladnik - 1 );
 }
 else /* Dla wykładnika parzystego */ 
 {
  return potegowanie( podstawa * podstawa, wykladnik / 2 );
 } 
}

Komentarze

Popularne posty z tego bloga

Funkcja Zastap

Napisać funkcję char * Zastap (const char *napis) , która będzie usuwała z tekstu zawierającego liczby całkowite i litery, wszystkie znaki, które nie wchodzą w skład liczby. Pozostawione liczby mają być oddzielone jedną spacją. Nowy tekst jest zwracany jako wskaźnik do poprawionego napisu. Przykład: ‘’ 123 zl 50 zl 632   zl 56zl’’ Po przekształceniu: ‘’ 123 50 632 56” #include <stdio.h> #include <stdlib.h> #include <string.h> #define xmalloc(typ, ilosc) (typ*) _new((ilosc)*sizeof(typ)) void* _new(size_t rozmiar) { void* p; p = malloc(rozmiar); if(p == NULL) { printf("Brak pamieci!"); exit(0); } return p; } char *Zastap(const char *napis) { char *nowy = xmalloc(char, strlen(napis)); while( (*++napis) != '\0') { if( (*napis >= '0' && *napis <= '9') || (*napis == ' ' && *(napis+1) &

Wypełnianie tablicy losowymi liczbami.

#include <stdio.h> #include <math.h> #include <time.h> #define SIZE 30 int LosujTablice(int tablica[], int rozmiar); int WypiszTablice(int tablica[], int rozmiar); int main(void){ srand( (unsigned)time(NULL) ); int tablica[SIZE]; LosujTablice(tablica, SIZE); WypiszTablice(tablica, SIZE); return 1; } int LosujTablice(int tablica[], int rozmiar) { int i; for( i = 0; i < rozmiar; i++ ) { tablica[i] = rand()%10; // od 0 do 9 } return 0; } int WypiszTablice(int tablica[], int rozmiar) { int i; if(rozmiar <= 20) { for(i = 0; i < rozmiar; i++) { printf("%i ", tablica[i]); } } else { for(i = 0; i < 10; i++) { printf("%i ", tablica[i]); } prin