فیبوناچی ۱

مقدماتی:

یکسری  مفاهیم ابتدایی از دنباله ی فیبوناچی:

1. f(0) = 0 ; f(1) = 1 ;  f(n > 2) = f(n-1) + f(n-2);
   
2. Digits: 
   
   1. f(50)  :      10      digits
   2. f(100):       20      digits
   3. f(500):       105    digits
   4. f(1000):     210     digits
   5. f(4800):     1000   digits
      
3. Negative fibo:
   

   

   F−8

   F−7

   F−6

   F−5

   F−4

   F−3

   F−2

   F−1

   F0

   F1

   F2

   F3

   F4

   F5

   F6

   F7

   F8

   −21

   13

   −8

   5

   −3

   2

   −1

   1

   0

   1

   1

   2

   3

   5

   8

   13

   21

کد زیر با  اردر n  سری فیبوناچی از ۱ تا n را بدست می آورد اما نکته ای که باید اینجا به آن دقت کرد این است که سرعت رشد تعداد ارقام در فیبوناچی بسیار زیاد است. بدین صورت که اگر آرایه fibo از نوع int باشد n <= 45 و اگر long long  باشد n<=92 پس برای n>92 باید از روش دیگری استفاده کرد که در ادامه به بررسی آن می پردازیم.

fibo[0] = 0;  fibo[1] = 1;

for( int i = 0 ;  i <  n ; i++ ) //  n baraye int ۴۵ ba baraye long long kamtar az ۹۲ mibashad

    fibo[i] = fibo[i-1] + fibo[i-2];

البته فرمولی با اردر ۱ وجود دارد که به شرح زیر است:

اما به دلیل توان n که در این فرمول وجود دارد 

استفاده از این فرمول توصیه نمی شود.

متوسط:

برای محاسبه ی دنباله ی فیبوناچی ارقام بزرگتر از ۹۲ باید از آرایه ی ۲ بعدی استفاده کرد بدین صورت که درایه ی اول برای شماره ی فیبوناچی و درایه دوم برای رقم های فیبوناچی اختصاص پیدا می کند. {fibo[n][k برابر است با  رقم k از سمت راست برای(F(n.

طریقه ی محاسبه:

    fibo[0][0] = 0;    num[0] = 0;
    fibo[1][0] = 1;    num[1] = 0;
    for( int i = 2 ; i < 5000 ;i ++ )
    {
        for( int j = 0 ; j < 10005; j++ )
            fibo[i][j] = fibo[i-1][j] + fibo[i-2][j];
        for( int j = 0 ; j < 10005; j++ )
        {
            if(fibo[i][j] >= 10 )
            {
                fibo[i][j+1] += fibo[i][j] / 10;
                fibo[i][j] %= 10;
            }
            if( fibo[i][j] != 0 )        num[i] = j;
        }
    }
   

1. محتوای آرایه num درایه آخرین خانه ی پر شده  یا به عبارت دیگر آدرس آخرین رقم دنباله است.
2. در هنگام استفاده از متغیر fibo باید به این نکته توجه کرد که [fibo[i][0 رقم یکان و
     [ [fibo[i][ num[n آخرین رفم دنباله می باشد.

عملگرهای بیتی (بخش اول)

مقدماتی :

 یکی از مباحثی که همیشه به عنوان حاشیه در کلاس های آموزشی برنامه نویسی آموزش داده میشود عملیات بیتیست (bitwise operation )  که به نظر من یکی از مهم ترین مفاهیمی است که می تواند یک برنامه نویس حرفه ای را از یک برنامه نویس معمولی متمایز سازد.

خلاصه ای از این عملگرها را در زیر می بینید : 

01001000 &     01001000 |     01110010 ^         
10111000 =     10111000 =     10101010     01110010 !
--------      --------    --------     --------  
00001000        11111000        11011000      10001101  

 01110010 >>     01110010 <<
--------      --------
00111001        11100100

متوسط :

چند هم ارز با استفاده از عملگر های بیتی:

1. x % 2 :                                                  x&1
2. pow( 2 , k ) :                                        1<<k
3. x % pow(2 , k )   :                                x & ( (1<<k) - 1 )
4. x* 2k  :                                                 x<<k 
5. x / 2k :                                                  x>>k

 در بعضی از سوالات می توان با استفاده از این عملگرها فرایند مارک کردن یا به طور کلی فرایندهایی که شامل ۲ حالت ۰ و ۱  با وسعتی کمتر از۳۱  میباشد را بهینه کرد. برای این کار نیاز است که به تک تک بیت های متغیر دسترسی داشته باشیم و عملیات دلخواه را روی بیت انجام دهیم که در زیر به سه تا از مهمترین آنها اشاره کردم.

To “set” a bit :               a |= (1 << n);                                                             قرار دادن ۱

To “clear” a bit:            b &= ~(1 << n);                                                         قرار دادن ۰

To “toggle” a bit:          c ^= (1 << n);                         جایگزین کردن یک با صفر  ـ یا بالعکس

 پیشرفته:

ماسک کردن:‌

فرض کنید که می خواهیم باقیمانده ی یک عدد بزرگ  (برای مثال  ۱۲۳۴۵۶۷۸۹۰۱۲۳۴۵۶۷۸۹۰۱۲۳۴۵۶۷۸۹۰) به ۱۰۰۰۰۰ را بدست آوریم. چیزی که اینجا مشهود است نیازما تنها به چند رقم سمت راست است. ‍پس می توانیم برای overflow نکردن همواره چند رقم اول را نگه داریم. این عمل را من ماسک کردن می نامم.

   هدف از تعریف کردن ماسک این است که در بعضی از سوالات تقریبا Big number که در ادامه ی سورس متغیر با عملیات بیتی سر و کار دارد ابتدا می توانیم ماسک را بدین صورت تعریف کنیم.

#define MASK 0xFF. . .FFFF  (به مقدار لازم )

این عبارت برابر عدد ۱ . . .۱۱۱۱ می باشد.

سپس در طول برنامه (جاهایی که با افزایش متغیر همراه هستیم) از عبارت زیر استفاده می کنیم :

x &= MASK;

این عمل از overflow شدن متغیر جلوگیری می کند.