المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر
دنبال کنندگان ۳ نفر
این وبلاگ را دنبال کنید

سوال پنجم Project Euler(همراه راه حل)

دوشنبه, ۱۸ دی ۱۳۹۱، ۰۸:۰۹ ب.ظ

متن سوال:

2520کوچکترین عددی است که بر تمام اعداد یک تا ده بخش پذیر است.

کوچکترین عددی که بر تمام اعداد یک تا بیست بخش پذیر باشد چند است؟ 

حل:

روش اول:

مثل همیشه تک تک حالات رو میشماریم.چون باید بر 20 هم بخش پذیر باشد از 20 شروع می کنیم و بیستا بیستا میریم جلو.

اینم کدش:

int i = 20;
 
while (i %  2 != 0 || i %  3 != 0 || i %  4 != 0 || i %  5 != 0 ||
         i %  6 != 0 || i %  7 != 0 || i %  8 != 0 || i %  9 != 0 ||
         i % 10 != 0 || i % 11 != 0 || i % 12 != 0 || i % 13 != 0 ||
         i % 14 != 0 || i % 15 != 0 || i % 16 != 0 || i % 17 != 0 ||
         i % 18 != 0 || i % 19 != 0 || i % 20 != 0) {
    i += 20;
}
The smallest number dividable with all number 1-20 is 232792560
Solution took 125 ms
روش دوم :
ما می تونیم این سوالو  با دست هم می تونیم حساب کنید .
خوب اول که 2 رو باید داشته باشیم چون باید به 1 تا 20 بخشپذیر باشه.
بعدش باید به سه هم بخشپذیر باشه ولی الان نیست پس عدد رو ضرب در 3 می کنیم 3*2
بعد می رسیم به 4 عدد ما یکی 2 کم داره تا بر چهار بخشپذیر باشه پس 3*2*2
بعد ضرب در 5 می کنیم 5*3*2*2
خوب الان میرسیم به 6 ولی این جا نباید هیچ کاری کنیم چون عدد ما به به 6 بخشپذیره چون 3*2=6وما تو عددمون 3*2 رو داریم همینجور ادامه می دیم . تا به جواب برسیم .
اینم کدش:

long long sum=1;
for(int a=2;a<=20;a++){
if(sum%a!=0){
sum = sum*a;
cout<<a<<" ";
}
}
cout<<(sum/24);

در اینجا ما حاصل رو تقسیم به 24 کردیم چون وقتی میرسه به 4اونو ضرب در 2 نمی کنه ضرب در 4 می کنه ولی این تو زمانی که به 8 میرسیم خود به خود خنثی میشه ولی تو ی 16 به جای اینکه عدد رو ضرب در 2 کنه ضرب در 16 می کنه پس تا حالا یکی ضرب در 8(دو به توان سه) اضافی هست.
در مورد 9 هم همین طور یکی 3 اضافه داریم .پس باید تقسیم بر 24 (8*3)بکنیم.
حاصل برابر خواهد بود با:232792560

نظرات (۰)

هیچ نظری هنوز ثبت نشده است
ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی