kburnik

C++ Binarna pretraga - K-ti korijen - callback funkcije

Oct 27th, 2012
130
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. TEMA : Računanje K-tog korijena
  4.  
  5. Autor zadatka: Kristijan Burnik, udruga informatičara Božo Težak
  6.  
  7. Autor rjesenja: Kristijan Burnik, udruga informatičara Božo Težak
  8.  
  9. Datum rjesavanja: 2012-10-27
  10.  
  11. */
  12. #include <iostream>
  13. #include <cstdlib>
  14.  
  15.  
  16. using namespace std;
  17.  
  18. // preciznost tipa podatka
  19. typedef long double real;
  20.  
  21.  
  22. // prototip callback funkcije
  23. typedef real (*Callback)(real a, real b);
  24.  
  25.  
  26. // preciznost računanja
  27. const real preciznost = 0.0000000001;
  28.  
  29. // binarana pretraga
  30. real binarno(real s, real e, real p, real n, Callback cmp) {
  31.      real t = 0;
  32.      
  33.      // dok je razlika gornje i donje granice veća od zadane preciznosti
  34.      while  ( (e-s) > p ) {
  35.             // računanje sredine - odabiremo kandidata za usporedbu
  36.             t = (s+e)/2;            
  37.            
  38.             // poziv callback funkcije, samo ovdje se koristi parametar n !
  39.             real usp = (*cmp)(t,n);
  40.            
  41.  
  42.             if ( usp > 0 && (usp <= p) || usp < 0 && (-usp <= p)) {
  43.                // ako je rješenje unutar zadane preciznosti
  44.                return t;  
  45.                                          
  46.             } else if (usp < 0) {
  47.               // rješenje je u gornjoj polovici intervala
  48.               s = t;      
  49.              
  50.             } else {
  51.               // rješenje je u donjoj polovici intervala
  52.               e = t ;
  53.              
  54.             }
  55.      }
  56.      return t;    
  57. }
  58.  
  59.  
  60. // k-ti korijen, moramo drzati globalno zbog prototipa funkcije usporedbe
  61. unsigned int k = 2;
  62.  
  63. // callback funkcija za usporedbu, racunamo (t^k - n)
  64. real razlika(real t, real n) {
  65.      real potencija = 1;
  66.      for (int i = 0; i < k; i++) potencija *= t;
  67.      return (potencija - n);
  68. }
  69.  
  70.  
  71.  
  72. // funkcija koja racuna korijen iz N po zadanom stupnju korijenovanja
  73. real korijen (real n, int stupanj) {
  74.      // binarano pretrazi interval [1,n] s preciznoscu preciznost
  75.      // --> trazi korijen od n po callback funkciji za usporedbu "razlika"
  76.      // postavi stupanj korijenovana globalno
  77.      k = stupanj;
  78.      return binarno(1,n,preciznost,n,razlika);
  79. }
  80.  
  81.  
  82. int main() {
  83.  
  84.     real n;
  85.     unsigned int stupanj;
  86.     // n je broj pod korijenom, stupanj je stupanj korijenovanja (stupanj >= 2)
  87.     cin >> n >> stupanj;
  88.  
  89.     // pozovi funkciju za korijen i ispisi rezultat
  90.     cout <<  korijen(n,stupanj) << endl;
  91.  
  92.     system("pause");
  93.     return 0;
  94. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×