ماراتن ++C
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
[center:4230d03519]
[/center:4230d03519]من بالاخره این سوال رو گرفتم. نکته ی جالبی داره!
معلومه که تجزیه ی عدد مشکل اصلی ماست.
حالا یه ایده می زنیم. ببینید عدد مبنای ما حداکثر ۵۰۰ میلیون است. پس هر کدام از k ها را که تجزیه کنیم یا اول است یا یک عامل اول کمتر از sqrt(500000000) دارد. همه ی اعداد اول کمتر از sqrt(5*10^7) را پیدا می کنیم و در یک vector یا آرایه می ریزیم. ــ زمان صفر!! ــ بعد برای تجزیه ی هر عدد از اینها استفاده می کنیم. وقتی بخواهیم k را تجزیه کنیم ابتدا k را با اولین عدد لیست می سنجیم که ببینیم بخشپذیر هست یا نه بعد اگر بخشپذیر بود تا جای ممکن بر عدد داخل لیست تقسیمش می کنیم و همینطور پیش می ریم. اگر در نهایت k=1 بشه که تجزیه تمومه در غیر این صورت k اولیه یک عامل اول بزرگتر از اون sqrt داشته که نتیجه می گیریم k فعلی اوله چون همه ی عوامل اول قبلی رو حذف کرده ایم.
پس تجزیه خیلی سریعتر می شه.
این هم کد من:
http://snipt.net/goharshady/factorials-again-acm
البته تو این کد اعداد اول رو از قبل save کرده ام.
معلومه که تجزیه ی عدد مشکل اصلی ماست.
حالا یه ایده می زنیم. ببینید عدد مبنای ما حداکثر ۵۰۰ میلیون است. پس هر کدام از k ها را که تجزیه کنیم یا اول است یا یک عامل اول کمتر از sqrt(500000000) دارد. همه ی اعداد اول کمتر از sqrt(5*10^7) را پیدا می کنیم و در یک vector یا آرایه می ریزیم. ــ زمان صفر!! ــ بعد برای تجزیه ی هر عدد از اینها استفاده می کنیم. وقتی بخواهیم k را تجزیه کنیم ابتدا k را با اولین عدد لیست می سنجیم که ببینیم بخشپذیر هست یا نه بعد اگر بخشپذیر بود تا جای ممکن بر عدد داخل لیست تقسیمش می کنیم و همینطور پیش می ریم. اگر در نهایت k=1 بشه که تجزیه تمومه در غیر این صورت k اولیه یک عامل اول بزرگتر از اون sqrt داشته که نتیجه می گیریم k فعلی اوله چون همه ی عوامل اول قبلی رو حذف کرده ایم.
پس تجزیه خیلی سریعتر می شه.
این هم کد من:
http://snipt.net/goharshady/factorials-again-acm
البته تو این کد اعداد اول رو از قبل save کرده ام.
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
این هم کد تستری هست که برای این سوال نوشتم:http://www.codeupload.com/807
سوال بعدی
محیط Allaame_Helli_Tehran_Olympiad_Algorithm_Class سوال LCS )
======================================================
کد من اینه ولی نمی دونم کجاش مشکل داره؟!؟
آقای گوهرشادی می شه مشکلشو بگید!؟
http://snipt.net/rezashiri/lcs-lcs
محیط Allaame_Helli_Tehran_Olympiad_Algorithm_Class سوال LCS )======================================================
کد من اینه ولی نمی دونم کجاش مشکل داره؟!؟
آقای گوهرشادی می شه مشکلشو بگید!؟
http://snipt.net/rezashiri/lcs-lcs
حالا مشکل این چیه!؟!
الگوریتمم:
از عدد اول در دنباله اول شروع می کنیم و یکی یکی تعداد دنباله های مشترک بعد از اون عدد رو پیدا می کنیم.
مثلا برای ورودی زیر:
4 4
1 2 3 5
5 2 3 1
اول می یایم 5 رو بررس می کینم که می شه 1 ، بعد می یایم3 رو بررسی می کنیم که می شه 2 تا و ...
آخرشم بزرگترین رو که پیدا کردیم اعضای دنباله مشترکشو چاپ می کنیم!
خودم نفهمیدم چی گفتم!
بعید میدونم شما هم ازش سر در بیارین!
الگوریتمم:
از عدد اول در دنباله اول شروع می کنیم و یکی یکی تعداد دنباله های مشترک بعد از اون عدد رو پیدا می کنیم.
مثلا برای ورودی زیر:
4 4
1 2 3 5
5 2 3 1
اول می یایم 5 رو بررس می کینم که می شه 1 ، بعد می یایم3 رو بررسی می کنیم که می شه 2 تا و ...
آخرشم بزرگترین رو که پیدا کردیم اعضای دنباله مشترکشو چاپ می کنیم!
کد
#include <cstdio>
//#include <conio.h>
int main()
{
int na,nb,a[10000],b[10000],tedad[1000],minj=0,sum=0,maxi,max=0;
scanf("%d%d",&na,&nb);
for(int i=0;i<na;i++)
scanf("%d",&a[i]);
for(int i=0;i<nb;i++)
scanf("%d",&b[i]);
start:
tedad[sum]=0;
for(int i=sum;i<na;i++)
{
for(int j=0;j<nb;j++)
{
if(a[i]==b[j] && j>=minj) {minj=j; tedad[sum]++;}//peida kardan tedad zirdonbale moshtarak
}
}
if(tedad[sum]>max){max=tedad[sum]; maxi=sum;}
if(sum<na){
minj=0;
sum++;
goto start;
}
printf("%d",tedad[maxi]);
minj=0;
for(int i=maxi;i<na;i++)
{
for(int j=0;j<nb;j++)
{
if(a[i]==b[j] && j>=minj) {minj=j; printf("\n%d %d",i+1,j+1);}//print zirdonbale ha
}
}
//getch();
return 0;
}
اینم با کامنت گذاری:
مثلا فرض کنید ورودی به صورت زیر است:
اول می آد تعداد اعضا زیر دنباله ای که از عدد 9 شروع می شن رو حساب می کنه ، بعد همین کار رو برای 6 و ...
بیشترین تعداد اعضا رو در خروجی چاپ می کنه بعدشم چون عددی که از آن شروع بشود این تعداد بدست می آید رو داریم پس حالا از اون عدد شروع می کنیم و خروجی هارو یکی یکی چاپ می کنیم.
امیدوارم متوجه شده باشید...
کد
#include <cstdio>
//#include <conio.h>
int main()
{
int na,nb,a[10000],b[10000],tedad[1000],minj=0,sum=0,maxi,max=0;
scanf("%d%d",&na,&nb);
for(int i=0;i<na;i++)
scanf("%d",&a[i]);
for(int i=0;i<nb;i++)
scanf("%d",&b[i]);
start:
tedad[sum]=0;
for(int i=sum;i<na;i++)
{
for(int j=0;j<nb;j++)
{
if(a[i]==b[j] && j>=minj) {minj=j; tedad[sum]++;}// .شروع مي شوند sum پيدا کردن تعداد زير دنباله هايي که از
}
}
if(tedad[sum]>max){max=tedad[sum]; maxi=sum;}
if(sum<na){
minj=0;
sum++;
goto start;//عددي که از آن شروع مي شود يکي بيشتر مي شود
}
//az inja be bad ke bishtarin tedad ro peida kardim , adidi ke age az on adad donbale shoro besha bish tarin tol ro dare
printf("%d",tedad[maxi]);
minj=0;
for(int i=maxi;i<na;i++)
{
for(int j=0;j<nb;j++)
{
if(a[i]==b[j] && j>=minj) {minj=j; printf("\n%d %d",i+1,j+1);}//print zirdonbale ha
}
}
//getch();
return 0;
}
کد
4 4
9 6 7 8
8 6 7 9بیشترین تعداد اعضا رو در خروجی چاپ می کنه بعدشم چون عددی که از آن شروع بشود این تعداد بدست می آید رو داریم پس حالا از اون عدد شروع می کنیم و خروجی هارو یکی یکی چاپ می کنیم.
امیدوارم متوجه شده باشید...