TC SRM #518 Third level

فرض کنید که ۲۰ سکه روی میزی قرار دارد به این صورت که روی سکه ها به سمت بالاست. ابتدا ۲ تا از این سکه ها رو به صورت شانسی بر عکس می کنیم. بدیهیست که ۱۸ تا سکه رو و ۲ سکه پشت داریم. حالا ۵ سکه را از بین این ۲۰ سکه به صورت شانسی انتخاب می کنیم. تعداد سکه هایی که رو و پشت هستند تغییر می کند. تعداد سکه های مورد انتظار بعد از تعدادی پشت و رو کردن به صورت شانسی را به چه صورت می توان بدست آورد.

در این سوال  تابع دو ورودی دارد. ۱- تعداد سکه  ۲- آرایه ای از تعداد سکه هایی که در هر مرحله باید به صورت شانسی انتخاب شوند و برعکس شوند. تعداد سکه ها بین ۱ و ۱۰۰۰ و سایز آرایه حداکثر ۵۰ می باشد.

می خواهیم ۵ تا سکه از این ۲۰ سکه انتخاب کنیم. ۱۸/۲۰ احتمال دارد که از سکه های رو و ۲/۲۰ احتمال می رود که از سکه های پشت انتخاب کنیم و آنها را برعکس کنیم. سکه های رویی که انتخاب می کنیم چون به صورت پشت قرار میگیرند از تعداد سکه های رو کم می شود و تعداد سکه هایی که از سکه های پشت انتخاب می کنیم به سکه های رو اضافه می شود به عبارت دیگر:

HEAD = HEAD - HEAD * ( a[i] / N) + (N- HEAD ) * ( a[i] / N ) ;

نکاتی که توی این فرمول باید دقت کنید CAST به دابل می باشد.

کد کامل :

double expectedHeads(int N, vector <int> a) {

double k = N ni = N;;

double

for( int i = 0 ; i < a.size() ; i++ ) {

k = k - (k )* (a[i]/ni) + ((ni-k)) * (a[i]/ni) ;

}

return k;

}

TC SRM #500 Third level

   این سوال از برنامه نویس می خواهد تا برنامه ای بنویسد که تعداد جواب های متمایز دو معادله را بدست آورد. صورت سوال بسیار ساده و قابل فهم می باشد اما نکته ای که باعث میشود این سوال برنامه نویس را به چالش بکشد این است که جواب های معادله ممکن است از مرز حافظه های قابل استفاده در زبان برنامه نویسی عبور کند و عددی با۱۰۰۰۰۰ رقم تولید کند.

   برای حل این سوال می بایست جواب های معادله را به وسیله ی تکنیکی به دو بخش تقسیم کنیم. این دوبخش حاصل باقیمانده ی جواب به دو عدد متفاوت است. ( انتخاب دو عدد متوالی ترجیح داده می شود ) برای مثال دو عدد ۱۰۰۰۰۰۰۰۰۱ و ۱۰۰۰۰۰۰۰۰۲ . اینجا دیده میشود که عدد ۱ به صورت ۱ و ۱ بدست می آید و عدد ۱۰۰۰۰۰۰۰۰۳ به صورت ۱ و ۲ به دست می آید . این روش تا عددی با تعداد ۱۰ به توان ۱۰ رقم را میتواند پشتیبانی کند !!!!

   ما ابتدا یک set از نوع pair می سازیم و شروع به بدست آوردن جواب ها به صورت موازی در دو متغیر می کنیم و باقیمانده دو متغیر را به عدد باقیمانده ی مربوط به متغیر بدست می آوریم و جایگزین متغیر می کنیم و آنها را در داخل ست وارد می کنیم.

این کد فقط برای یکی از معادلات هست :

st.insert( point(b1 , b1 ) );

long long a = b1 , b = b1;

for( int i = 0 ; i < n1-1 ; i++ ) {

a *= q1 ;

b *= q1 ;

a %= m1;

b %= m2;

st.insert( point( a , b) );

}

معادله ی دیگر نیز به همین شکل بدست می آوریم و داخل ست می کنیم. سایز ست جواب سوال می باشد.

حل معادلات ریاضی (۱)

متوسط:

برای تقریب جواب معادلات ریاضی توسط کامپیوتر (با هر اندازه دقت) می توانیم از سه روش استفاده کنیم که به طور اختصار و کاربردی دو روش را در این پست و روش سوم که روش نیوتن است در پستی جداگانه بررسی می کنیم. 

نکته ای که باید قبل از بررسی روش ها توجه کنید این است که معادله را باید بتوان به صورت f(x) =0 تبدیل کرد که ما در مثال های که در ادامه ذکر می کنیم تابع معادله به صورت ( double f(double x تعریف شده است. نکته ی دیگر اینکه بازه ای که معادله دارای جواب است را بدانیم که ما به طور پیش فرض بازه ی جواب معادله را بین ۰ و ۱ در نظر گرفته ایم.

Bisection method :

این روش با روش جست و جوی دودویی مشابهت زیادی دارد. با این تفاوت که ما در بررسی پیشروی بازه ی جواب به جای بررسی تفاوت( کوچکی و بزرگی‌) به بررسی تغییر علامت های دو نقطه ی بالایی و پایینی می پردازیم.

کد سی این برنامه به این صورت است:

if(f(0) * f(1) > 0)
        printf( "No solution\n" );        

else {

    for( u = 0 , v = 1 ;  v - u >= Precision ; )     // be jaye Precision mizan deghat gharar migirad masalan 0.0001

   {              c = (v + u)/2;
         if(  f( c ) * f(u) > 0)     u = c; 

         else                             v = c;
   }
        printf("%0.4lf\n" , u );
}

 

Secant method :

این روش نیز مانند روش قبلی با دو نقطه به عنوان ابتدا و انتهای محدوده ی جواب آغاز می شود. این روش بدین صورت است که در هر مرحله نقطه ی جدیدی بوجود می آید و ادامه ی کار با این نقطه و نقطه ی بوجود آمده ی قبل از آن از سر گرفته می شود. طریقه ی بوجود آمدن هر نقطه بدین صورت است که خطی که از دو نقطه ی آخر عبور می کند را با خط افقی محور تلاقی می دهیم. نقطه ی تلاقی این خط با محور نقطه ی جدید است. به عبارت دیگر اگر به ترتیب نقطه های X0 و X1 را داشته باشیم نقطه ی X2 به این صورت بوجود می آید :

معادله خط گذرنده از دو نقطه :

اگر y = 0 آنگاه  X2  برابر است با :

 یکی از روش های پیاده سازی Secant بدین شکل می باشد :

if(f(0) * f(1) > 0)
        printf( "No solution\n" );        

else {

    for( u = 0 , v = 1 ; ; )   

   {
            fu = f(u);
            fv = f(v);
            if( fabs(fv -fu) < Precision ) // be jaye Precision mizan deghat gharar migirad
                break;
            c = v - fv * ( v - u ) / (fv - fu) ;
            swap( u , v );   u = c;
   }

        printf("%0.4lf\n" , u );

}

روش دیگر پیاده سازی :

if(f(0) * f(1) > 0)
        printf( "No solution\n" );        

else {

    for( u = 0 , v = 1 ; ; )   

   {
            fu = f(u);
            fv = f(v);
d = f(v)*(v-u)/(f(v)-f(u)); if (fabs(d) < EPS) break; u = v; v = v - d;    }

        printf("%0.4lf\n" , v );

} 

442 - Matrix Chain Multiplication

دسته  : ad hoc

توضیح سوال: ابتدای ورودی لیستی از ماتریس ها که شامل نام و اندازه ی ماتریس ها می باشد داده می شود. اسم ماتریس حروف بزرگ می باشد که از ۲۶ تا ماتریس بیشتر نمی تواند باشد. بعد از آن لیستی شامل پرانتز ها و  اسامی ماتریس ها داده می شود که شما می بایست تعداد عملیاتی که برای محاسبه ی این عبارت انجام می شود را به عنوان خروجی چاپ کنید این نکته هم نباید فراموش شود که ممکن است عبارت قانون ضرب ها را رعایت نکند که در این صورت باید error چاپ شود.

در سوال بر اساس Extended Backus–Naur Form قوانینی که بر اجرای آنها تاکید شده است داده شده که بدین شرح است.

SecondPart = Line { Line } <EOF>
Line       = Expression <CR>
Expression = Matrix | "(" Expression Expression ")"
Matrix     = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

براساس Extended Backus–Naur Form :

=            defining-symbol تعریف

{ ... }                      repetition تکرار

|                    alternation ترتیب

نکات خوبی از این قوانین میشه استخراج کرد برای مثال از قسمت Expression که به صورت بازگشتی تعریف شده میشه فهمید که داخلی ترین پرانتز فقط شامل دو ماتریس است نه کمتر و نه بیشتر.

.

توضیح راه حل: اگر شما بتوانید از پس نمونه ورودی های این سوال بر بیایید به راحتی Accepte این سوال رو خواهید گرفت. برای اطمینان summation یا به عبارت دیگر خروجی را long long بگیرید. 

کاری که می بایست انجام دهید این است که شروع به وارد کردن عبارت در داخل stack کنید. زمانی که به '(' رسیدید باید به پردازش دو عنصر آخر که حتما دو ماتریس است بپردازید و بعد سومین عنصر آخر stack که ')' به همراه دو ماتریس از stack خارج کنید و ماتریس حاصلشان را داخل stack قرار دهید.

با استفاده از یک vector از نوع pair می توانید به ماتریس های  لیست اول ورودی و ماتریس های جدیدی که در عبارت بوجود می آید دسترسی پیدا کنید.

 پیشنهاد من این است که نوع stack از نوع int  باشد که در این صورت ماتریس ها را با ایندکس vector و ')' را منفی یک قرار دهید.

فیبوناچی ۱

مقدماتی:

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

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 شدن متغیر جلوگیری می کند.