سوال راجع به تکرار اعداد؟

[storm_saeed]

سلام دوستان
سوال من اینه n تا عدد میدیم عددی که بیشتر از n/2 بار تکرار شده رو بگیم چیه . سوالش آسونه یه الگوریتم ساده هم داره که اعداد رو به افراز ها [n/2] تبدیل کنیم و تو هر کدوم چک کنیم اعداد برابرند یا نه ...
ولی مشکل اینجاست با آرایه نوشتنش کاری نداره ولی بدون آرایه چطور میشه این برنامه رو نوشت ؟ کسی ایده ای داره ؟ممنون

[omidshaman]

اول sort کن .
بعد تکراریا رو در بیار .

[storm_saeed]

خب بدون آرایه چطور sort کنم ؟ تو چیزی نمیتونم بریزم که

[rahnema1]

از الگویی که در الگوریتم heap sort استفاده شده بهره ببرید

[omidshaman]

الگوریتم sort زیاده بدون آرایه هم میشه sort کرد.
http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

[rahnema1]

اگر از الگوی heap sort استفاده بشه لازم نیست کل آرایه رو sort کنیم فقط لازمه حداکثر تا نصف اون انجام بشه ونکته دیگه اینکه اصلا آرایه sort شده لازم نیست ایجاد بشه
تو اینجا فقط لازمه تعداد شمرده بشه

[storm_saeed]

کلا ما باید از o(1) استفاده کنیم با مرتب سازی نمیشه اینکارو کرد

[rahnema1]

افراز کردن که میره تو مقوله فاکتوریل!!!!

[storm_saeed]

نه اون راهی که گفتم با ارایه حل میشه به افراز های n/2تبدیل میکنیمو...
الان مشکل اینه بدون آرایه بریم چطور میشه.

[rahnema1]

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

[storm_saeed]

نه من فقط میخوام این برنامه رو فقط با استفاده از if for while switch استفاده کنم کلا هدفم اینه
اینطوری مساله جالبی میشه

[rahnema1]

فکر نکنم جالب باشه در هر صورت با فرض این مورد، شما می تونید از عنصر اول آرایه ای که مقادیر توش ذخیره شده شروع کنید وبرای اون تمام عناصر را بگردید و مقادیر مشابه را پیدا کنید به همین ترتیب تا عنصر آخر بروید و برای انها هم این کار را بکنید
نهایتا این الگوریتم با کارایی (O(n^2 خواهد بود

[storm_saeed]

باید یه راحی بریم که O(1) بشه بدون آرایه واینجور چیزا کلا سوال جالبو سختیه من تا یه جاهایش نوشتم به دوتا مجموعه افراز میکنیم(n/2) تایی یبار n/2 تا عدد میگیرم ومقایسه روشون انجام میدیم بعد n/2 تای بعدی بعد اگه فرد بود وسطیم نگه میداریم و مقایسشون میکنیم راه سادش با استفاده از آرایه گرفتن میانه هست .

[rahnema1]

داده های ورودی یا همون n تا عددی که می دهیم کجا می خواهد باشه تو آرایه یا جای دیگه منظورم از آرایه اینه

[omidshaman]

با (O(1 که نمیشه نوشت اصلا !!
(O(n منظوزته ؟!

[storm_saeed]

با o(1)
چرا نوشتن . خودمم الگوریتمشو فهمیدم باید چیکار کرد فقط نوشتنش یکم سخت شد برام

[rahnema1]

دوست عزیز با صحبت کردن مشکل حل نمی شه لطفا الگوریتم یا برنامه نوشته شده رو بذار ببینیم چه جوریه

[storm_saeed]

اینو نوشتمش order 1 از حافظه میگیره و o(n) که به تعداد گذفتن ورودی ها

#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;

int a,b,c,d,temp=0,sum1,sum2,counter=0;
cin>>a>>b;
temp+=2;
if(a==b)
sum1=a;
else
sum1=0;
if(sum1!=0) ++counter;
while(temp<=n){
if(counter*2> n/2){
sum2=sum1;
break;}
x:if(temp<=n){
cin>>c;
++temp;
if(temp==n && sum1==0 && sum2==0){
sum2=c;
break;
}
else if(temp==n && (sum1!=0 || sum2!=0))
{
sum2=sum2?sum2!=0:sum1;
break;
}
}
if(temp<=n){
cin>>d;
++temp;
}

if(c==d){
if(sum1==0){
sum1=d;
goto x;}
else
sum2=d;
if(sum1==sum2)
++counter;
}
else
{if(sum1==0)
sum1=0;
else
sum2=0;
}
if(sum1!=sum2 && sum1!=0 && sum2!=0){
sum1=0;
sum2=0;}
else
sum2=0;
if(temp==n && (sum1==0 || sum2==0)){
sum2=sum1?sum1!=0:sum2;
break;
}
}
cout<<sum2;
}

فقط تو اعداد نباید صفر بدین
اگه عددی یافت نشه با این ویژگی ها یا صفر میده یا هیچی نشون نمیده
مثلا بدین 8
1 1 1 1 2 2 2 2
چیزی نشون نمیده اگه 2 بدیم 2 میده 1 بدیم 1 میده
وگرنه هرعدد دیگه بدیم صفر میده

یا مثلا بدیم
5
1 1 1 2 2
1 میده

[hadi0x7c7]

واسه این ورددی که درست جواب نداد!

10
1 2 10 7 7 7 7 7 7 7
1

[storm_saeed]

اره
من الگوریتمم اینه 2 تا دوتا عدداروبگیره بعد ببینه برابرن یانه بعد روشون مقایشه انجام بده
مثلا 12 رو میگیره میبینه برابر نیستن میرزه دوربعد 10 و 7 اوناهم برابر نیستن میریزن دور ولی بعدیا برابرن نیگرشون میداره
کلا سخته خیلی حالتا پیش میاد

[rahnema1]

اولا که الگوریتم جواب نمیده ثانیا اگه فرضتون این باشه که بین تمام ورودی ها فقط دو ورودی مجزا باشه مثل 2222222211111 و اومدین دو تا متغیر هم تعریف کردید که تعداد تکرار رو توی اونها ذخیره کنید دیگه چه فرقی با آرایه کرد؟ نکنه می خواهید به تعداد ارقام مجزا متغیر تعریف کنید؟
فقط این نکته رو بگم برای شمردن تعداد ارقام مجزا راهی نیست مگر اینکه به تعداد ارقام مجزا متغیر تعریف بشه یا آرایه ای یا ساختاری به همان طول ایجاد بشه چون لازمه مراجعه مکرر به اونها بشه

[storm_saeed]

نه تویه While به تعداد n عدد میگیریم
الگوریتمش یه همچین چیزیه
خب شما راهتون چیه
(معلم ما این سوال رو بدون آرایه حل کرده حالا این سوال رو بما داده حل کنیم)
مثلا 2222222211111
من تو کد تعریف کردم اگه تا n/2+1 بار یه عدد پشت سر هم اومد همونو بگه و بپره بیرون از برنامه .
کلا خیلی حالات پیش میاد

[rahnema1]

دوست عزیز همون طور که قبلا گفتم باید شما هنگام دریافت هر ورودی اگه به یک مقدار مجزا که با مقادیر ورودی قبلی متفاوته مواجه شدید یک مدخل برای اون توی یک ساختار مانند یک لیست ، یک درخت یا یک آرایه ایجاد کنید و مقادیری که برای آن پیش می آید را تعدادشون رو توی اون مدخل ذخیره کنید راهی جز این نیست نهایتا اون ساختار تعداد عناصرش به تعداد مقادیر مجزای ورودی خواهد بود و نکته دیگه اینکه برای اینکه بفهمیم عنصر ورودی با عناصر قبلی مجزا است یا نه با باید به همون ساختار مراجعه کنیم و توی اون جستجو کنیم به همین خاطر من می گم یک درخت باشه که جستجو توی اون راحت باشه

[storm_saeed]

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

[storm_saeed]

این لینک و ببینید

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html


#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
int ans,counter=0,a,temp=0;
while(temp<n){
cin>>a;
if(counter==0)
{
counter=1;
ans=a;
}
else{
if(counter>0){
if(ans==a)
++counter;
else
--counter;
} }
++temp;
cout<<counter;
}
if (counter>0)
cout<<"The number "<<ans<<" is in the more majority ";
}
فقط تنها مشکلش اینه که فرض میکنه عددی باشه که بیش از n/2 بار تکرار شده باشه

[rahnema1]

دست شما درد نکنه خیلی الگوریتم جالبی بود ولی یک نکته فراموش نشه و خودش صاحب مقاله هم اعلام کرده که با این الگوریتم حداکثر 2n مقایسه لازمه انجام بشه و این معنیش اینه که باید داده ها در یک آرایه ذخیره شده باشند توی کد فرترن هم لیبل 200 کارش همینه که برای بار دوم آرایه رو جستجو می کنه

[storm_saeed]

میشه یه نگاه به این کد بندازید


#include <iostream>
using namespace std;
int main(){
int n;
bool ch=0;
cin>>n;
int m=0,ans,counter=0,a,lastlast=0,last,temp=0;
while(temp<n){
cin>>a;
if(!counter)
{
counter=1;
if(last==a)
ans=a;
else{
if(ans!=-1)
lastlast=last;
last=a;
ans=-1;

}
}
else if(last==a)
{
if(counter>m){
ans=last;
ch=1;}
counter++;
if(counter>m)
m=counter;
}
else
counter--;
if(counter>n/2){
cout<<ans;
return 0;}
if(ch==0 && temp==n/2+1){
cout<<"-s1";
return 0;}

++temp;}
if(counter==0 )
ans=-1;
if(last==lastlast)
ans=last;
cout<<ans;
}


ببینید کجاهاش غلطه
توی صفحه الگوریتم نوشته این الگوریتم موقعی کاربرد داره که ما میدونیم یه عدد بیش از n/2 تکرار شده ولی نمیدونیم چه عددیه تو stackoverflow پرسیدم میگن میشه با همین الگوریتم فرض مساله که فرض کردیم n/2 بار تکرار شده رو حذفش کنیم و سوالی که من پرسیدم رو باهاش حل کنیم

[storm_saeed]

خب اون کد غلطه یجاهایش این تصحیح شدش


#include <iostream>
using namespace std;
int majority(int n,int &ans,int counter){
int a,i;
if (!n) return 0;
cin>>a;
if (!counter) ans=a;
counter+=2*(ans==a)-1;
i=majority(n-1,ans,counter);
return i+(ans==a);
}
int main(){
int n,ans;
cin>>n;
if (n/2 < majority(n,ans,0))
cout<<"The number "<<ans<<" is in the more majority "<<endl;
else
cout<<"No majority"<<endl;
}

[rahnema1]

ببینید چون که لازمه حتما الگوریتم دو بار از روی داده ها عبور کنه بنابراین یا باید در آرایه ذخیره بشن یا یانکه با ترفندی که در زیر گذاشتم مشکلش حل میشه و اون اینه که یک تابع بازگشتی تعریف کنیم و داخل تابع تو در تو متغیری به نام A قرار داره که مقادیر ورودی رو ذخیره می کنه و چونکه در هر تابع local هست میتونه تمام ورودی ها رو در بر بگیره با این ترفند اگر چه از آرایه استفاده نکردیم اما به اندازه آرایه حافظه مصرف میشه تو تابع بازگشتی یک مرحله رفت هست و یک مرحله برگشت درست منطبق با دو دوری که الگوریتم اصلی روی داده ها میزنه



#include <iostream>
using namespace std;
int CAND,I=1,K=0,K1=0,N;
void rec();
int main(){
cin>>N;cout<<"-------"<<endl;
rec();
cout<<"Input Error";
return 0;
}
void rec(){
int A;
//raft
if (I<=N){
cin>>A;
if (K==0){
CAND=A;
K=1;
I++;
}
else {
if (CAND == A){
K++;
I++;
}
else {
K--;
I++;
}
}
rec();
}
//bargasht
if (I>N){
if (K == 0){cout<<"Input Error";std::exit(0);}
if (K > N/2){cout<<"----"<<endl<<CAND;std::exit(0);}
if (CAND == A){
K1++;
if (K1 > N/2){cout<<"----"<<endl<<CAND;std::exit(0);}
}
return;
}
}

[rahnema1]

چه تفاهمی در هم زمانی

[storm_saeed]

:)
کد من خط هاش کمتره D:

در واقع من از الگوریتم Linear Time Majority Vote Algorithm
استفاده کردم ولی بصورت بازگشتی چون این الگوریتم فرضش اینه عددی هست که بیش از n/2 تکرار شده