جستجو در دو آرایه دوبعد 1000 سطری

[yasemi]

من دوتا آرایه دوبعدی دارم مثل زیر




[int Start[1000][11;
int Gold[1000][11];



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


ممنون

[Pooria121]

البته بهتر بود شما کد خودتون رو بدید و ایرادش رو اینجا بیان کنید،



for(int i=0; i<1000;i++){
bool found = false;
for(int j=0;j<11;j++){
if(Start[i][j] == Gold[i][j]) found = true;
else found = false;
}
if(found == true) return true;
}

[mohsensaghafi]

سلام دوست عزیز.
سوال شما رو در بخش C و ++C و Delphi دیدم و جواب دادم. اما در قسمت الگوریتم شاید جواب شما فقط ارائه راه حل نباشه. اگه ممکنه توضیح بیشتر بدید. اگر راه حلی که گذاشتم جواب نداد بگید تا راه های دیگری پیدا کنیم.

[yasemi]

این نمونه کد نیست من میگم دوتا آرایه 1000 سطری که بتونیم یه سطر مشابه پیدا کنیم

لطفا مثال بزنید ممنون

[Pooria121]

این نمونه کد نیست من میگم دوتا آرایه 1000 سطری که بتونیم یه سطر مشابه پیدا کنیم

لطفا مثال بزنید ممنون


این کد اگر سطر i در array1 و سطر j در array2، در صورتیکه i = j باشه رو پیدا میکنه! حالا شما سوالت رو کامل بیان کن، شما میخوای j = i باشه یا نه مهم نیست که برابر باشند؟

که اگر i و j میخواهید باهم برابر نباشند، یک for دیگر باید اضافه کرد.



for(int i=0; i<1000;i++){
bool found = false;
for(ii = 0;ii<1000;ii++){
for(int j=0;j<11;j++){
if(Start[i][j] == Gold[ii][j]) found = true;
else found = false;
}
if(found == true) return true;
}

}

[yasemi]

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

[Pooria121]

راه سریعتر یا مجزا آسا وجود نداره برای مشکل شما، شما باید هر 2 تارو بگردید،
البته یک راه خیلی گنگتر است که تائثیر خاصی نداره، Dynamic Programming ولی اونهم زیاد تغییری فک نمیکنم بده.
شما میتوانید اگر ماپیوتر شما چند Core دارد؛ با استفاده از Thread، از اون کرها استفاده کنید، یک جورایی مانند Parallel Programming.
نصف جستوجو هارو مثلا Core1 بکند و نصف دیگر را Core2 اگر CPU شما Dual Core است.

[qwerty11]

راه سریعتر یا مجزا آسا وجود داره

از hash کردن استفاده کنید ... البته احتمالاً نمیدونین hash چیه اما به هر حال راه حل بهتر همیشه وجود داره ...

اگه حوصله داری یه نگاه به اینا بنداز :

http://en.wikipedia.org/wiki/Hash_table

http://en.wikipedia.org/wiki/Hash_function

[SAASTN]

اگه کد Pooria121 به شکل زیر تغییر پیدا کنه پیچیدگی از n^2 به nlogn کاهش پیدا می کنه.

for(int i=0; i<999;i++){
bool found = false;
for(ii = i+1;ii<1000;ii++){
...

ممنون از همگی اما این روش خیلی خیلی کنده روش دیگه ای بلد نیستید همینم به فکر خودم رسید ولی خیلی کنده
شما کافیه یک کتاب الگوریتم باز کنی، توش تمام روشهای مرتب سازی و جستجو نوشته شده، نیازی هم به فکر کردن نیست.
الگوریتم QuickSort نظرا از روش فوق سریعتره ولی توی n هزارتایی تاثیر محسوسی نداره.

[qwerty11]

اگه کد Pooria121 به شکل زیر تغییر پیدا کنه پیچیدگی از n^2 به nlogn کاهش پیدا می کنه.دوست عزیز واجبه که یه فلش بک به ساختمون داده بزنین ! الگوریتمی که شما گفتین بازم n^2 هستش ! ضمن اینکه اومدین درستش کنین زدین خرابترشم کردین :( حلقه ی دوم هم مثل حلقه ی اول باید از 0 شروع بشه. آخه مگه قراره آرایه رو سورت کنیم که اینجوری گفتین !؟

[SAASTN]

الگوریتمی که شما گفتین بازم n^2 هستش ! ضمن اینکه اومدین درستش کنین زدین خرابترشم کردین :( حلقه ی دوم هم مثل حلقه ی اول باید از 0 شروع بشه. آخه مگه قراره آرایه رو سورت کنیم که اینجوری گفتین !؟
ممنون از راهنمایی تون. چه ربطی به سورت کردن داره؟ قراره تمام موارد یک بار با هم مقایسه بشن و درصورتی که حتی یک مورد مساوی توی آرایه ها بود خروجی True باشه. حالا چه نیازی هست که حلقه دوم از صفر شروع بشه؟؟

[qwerty11]

حالا چه نیازی هست که حلقه دوم از صفر شروع بشه؟؟ چون عملیات داره روی 2 تا آرایه صورت میگیره. نه مثل سورت روی یه دونه آرایه !

اینم جواب من واسه این سوال : البته تو notepad نوشتم و تست نکردم. خلاصه کلیتش درسته.


bool test(int a[][], int b[][]){
int h[7001]={0};
for(int i=0;i<1000;i++){
int m=hash(a,i);
while(h[m]!=0)
m=(m+1)%7001;
h[m]=i+1;
}
for(int i=0;i<1000;i++){
int m=hash(b,i);
while(h[m]!=0){
if(eq(a, h[m]-1, b, i)) return true;
m=(m+1)%7001;
}
}
return false;
}


int hash(int c[][], int i){
int sum=0;
for(int j=0;j<11;j++){
sum+=(j+1)*c[i][j];
}
return abs(sum)%7001;
}

bool eq(int a[][], int i, int b[][], int j){
for(int k=0;k<11;k++)
if(a[i][k]!=b[j][k]) return false;
return true;
}

[mohsensaghafi]

ممنون از راهنمایی تون. چه ربطی به سورت کردن داره؟ قراره تمام موارد یک بار با هم مقایسه بشن و درصورتی که حتی یک مورد مساوی توی آرایه ها بود خروجی True باشه. حالا چه نیازی هست که حلقه دوم از صفر شروع بشه؟؟


فرض کن آرایه اولت این باشه


1,2,3,4,5,6,7,8,9,0,1
4,3,2,1,9,8,7,6,5,4,3
1,5,34,4,5,4,3,2,3,44,23
.
.
.

و فرض کن آرایه دومت این باشه

1,5,34,4,5,4,3,2,3,44,23
8,7,6,5,4,34,3,2,1,9,12
1,2,4,3,5,6,7,8,9,0,1
.
.
.
اون موقع اگر حلقه دوم از صفر شروع نشه، ردیف 3 از آرایه اول با ردیف 1 از آرایه دوم هیچگاه با هم مقایسه نخواهند شد.

[mohsensaghafi]

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

[SAASTN]

چون عملیات داره روی 2 تا آرایه صورت میگیره. نه مثل سورت روی یه دونه آرایه !
بنده آماده اجرای هرگونه حکمی هستم و شخصا اذعان می کنم که حداقل حکمی که میشه برای همچین سوتی ای درنظر گرفت عبارته از: مسواک، بوس، لالا، راس ساعت 23:30 و ممنوعیت ارسال هرگونه پست بعد از این ساعت به مدت شش ماه. البته در صورت صلاحدید دوستان حاضرم احکام سنگین تری رو هم اجرا کنم.
ما رفتیم برای یک فلش بک عمقی!:اشتباه:

[mohsensaghafi]

سلام. دوست من.


بنده آماده اجرای هرگونه حکمی هستم و شخصا اذعان می کنم که حداقل حکمی که میشه برای همچین سوتی ای درنظر گرفت عبارته از: مسواک، بوس، لالا، راس ساعت 23:30 و ممنوعیت ارسال هرگونه پست بعد از این ساعت به مدت شش ماه. البته در صورت صلاحدید دوستان حاضرم احکام سنگین تری رو هم اجرا کنم.

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