ماراتن الگوریتم

[SABB]

ميدونم ايني كه ميگم شبيه الگوريتم نيست ولي ....
اين كار ممكن است :‌
مثلا اول عدد 123 را به 132 تبديل مي كنيم ، بعد 4 بار با 102 جمع مي كنيم ، عدد حاصل 540 مي شود و بعد آن را به صورت 54 در مي آوريم و همين استراتي را در پيش
مي گيريم (اگه منظورم رو متوجه نشديد بگيد بيشتر توضيح بدم...)

متوجه نشدم!
ولی روشتون درسته، باید با همین کارا دوباره به عددی برسید که تو دنباله اعدادتون بوده.

 

[SABB]

ميدونم ايني كه ميگم شبيه الگوريتم نيست ولي ....
اين كار ممكن است :‌
مثلا اول عدد 123 را به 132 تبديل مي كنيم ، بعد 4 بار با 102 جمع مي كنيم ، عدد حاصل 540 مي شود و بعد آن را به صورت 54 در مي آوريم و همين استراتي را در پيش
مي گيريم (اگه منظورم رو متوجه نشديد بگيد بيشتر توضيح بدم...)

استراتژی

 

[Olympiad]

اگه متوجه نشدي پس چجوري فهميدي كه روشم درسته؟

 

[SABB]

اگه متوجه نشدي پس چجوري فهميدي كه روشم درسته؟

حدس زدم درسته

پ.ن. ولی شبیه راه من بود، برای همین یقین پیدا کردم.

 

[Olympiad]

اگه متوجه نشدي پس چجوري فهميدي كه روشم درسته؟

حدس زدم درسته

منظورم من اين بود كه سعي كنيم عدد صفر را ايجاد كنيم .... غلطه؟

 

[SABB]

اگه متوجه نشدي پس چجوري فهميدي كه روشم درسته؟

حدس زدم درسته

منظورم من اين بود كه سعي كنيم عدد صفر را ايجاد كنيم .... غلطه؟

میشه راهتون رو بنویسید؟!
راستی... وقتی صفر شد کامپیوتر دوباره عدد 102 را باهاش جمع می کنه.

 

[Olympiad]

اگه متوجه نشدي پس چجوري فهميدي كه روشم درسته؟

حدس زدم درسته

منظورم من اين بود كه سعي كنيم عدد صفر را ايجاد كنيم .... غلطه؟

میشه راهتون رو بنویسید؟!
راستی... وقتی صفر شد کامپیوتر دوباره عدد 102 را باهاش جمع می کنه.

مثلا عدد 123 به 132 تبديل سپس 4 بار با 102 جمع و به 540 تبديل ميشه ، آن را به 54 تبديل ميكنيم بعد 54 را 3 بار با 102 جمع
مي كنيم ميشه 360 ،آن را به 36 تبديل مي كنيم ، سپس 36 را 2 بار با 102 جمع مي كنيم مي شود 240 ، آن را به 24 تبديل مي كنيم و به همين ترتيب.....
درسته؟

 

[SABB]

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

 

[SABB]

[center:6c954af644]

الگوریتمی طراحی کنید که در گراف داده شده دوری با طول زوج به دست آورد. (منبع: مساله های الگوریتمی)​

[/center:6c954af644]

 

[SABB]

اگه متوجه نشدي پس چجوري فهميدي كه روشم درسته؟

حدس زدم درسته

منظورم من اين بود كه سعي كنيم عدد صفر را ايجاد كنيم .... غلطه؟

میشه راهتون رو بنویسید؟!
راستی... وقتی صفر شد کامپیوتر دوباره عدد 102 را باهاش جمع می کنه.

مثلا عدد 123 به 132 تبديل سپس 4 بار با 102 جمع و به 540 تبديل ميشه ، آن را به 54 تبديل ميكنيم بعد 54 را 3 بار با 102 جمع
مي كنيم ميشه 360 ،آن را به 36 تبديل مي كنيم ، سپس 36 را 2 بار با 102 جمع مي كنيم مي شود 240 ، آن را به 24 تبديل مي كنيم و به همين ترتيب.....
درسته؟

راهتون کاملا درسته

 

[Olympiad]

سلام !!!! .... گفتم اين تاپيك هم بياد تو كار !!!! يه 2 ماهي هست كه اين تاپيك خوابيده !!!

 

[Goharshady]

[center:0f0af5011a]

الگوریتمی طراحی کنید که در گراف داده شده دوری با طول زوج به دست آورد. (منبع: مساله های الگوریتمی)​

[/center:0f0af5011a]

از اون جایی که هیچ محدودیتی نداریم روی همه ی راسها bfs می زنیم. این می شه O n[SUP]3[/SUP] که خیلی هم بد نیست.

 

[Goharshady]

[center:3a0c67f16c]

[/center:3a0c67f16c]سوال هشتم:
در یک گراف جهت دار داده شده همه ی مولفه های همبندی و مولفه های قویا همبند ماکسیمال را پیدا کنید.

 

[Olympiad]

[center:e308f316cf]

الگوریتمی طراحی کنید که در گراف داده شده دوری با طول زوج به دست آورد. (منبع: مساله های الگوریتمی)​

[/center:e308f316cf]

از اون جایی که هیچ محدودیتی نداریم روی همه ی راسها bfs می زنیم. این می شه O n[SUP]3[/SUP] که خیلی هم بد نیست.

BFS ؟؟؟؟؟ چجوري هست !!!!!؟؟؟؟

 

[Goharshady]

لطفا یک کتاب الگوریتم بخرید و بخونید!!!
خیلی سخته که bfs رو توضیح بدم.
http://fa.wikipedia.org/wiki/الگوریتم_جستجوی_اول_سطح
http://en.wikipedia.org/wiki/Breadth-first_search

 

[Olympiad]

لطفا یک کتاب الگوریتم بخرید و بخونید!!!
خیلی سخته که bfs رو توضیح بدم.
http://fa.wikipedia.org/wiki/الگوریتم_جستجوی_اول_سطح
http://en.wikipedia.org/wiki/Breadth-first_search

CLRS ترجمه ي قمي خوبه بخرم !!؟؟؟

 

[Goharshady]

اگه ترجمه ی گروه خوارزمی رو پیدا کنی خیلی بهتره

 

[SABB]

[center:586030035e]

[/center:586030035e]سوال هشتم:
در یک گراف جهت دار داده شده همه ی مولفه های همبندی و مولفه های قویا همبند ماکسیمال را پیدا کنید.

ببخشید، مولفه همبندی توی گراف جهت دار مثل همون مولفه همبندی تو گراف معمولیه؟ و مولفه قویا همبند چیه؟

 

[Goharshady]

[center:d0c7e3cd93]

[/center:d0c7e3cd93]سوال هشتم:
در یک گراف جهت دار داده شده همه ی مولفه های همبندی و مولفه های قویا همبند ماکسیمال را پیدا کنید.

ببخشید، مولفه همبندی توی گراف جهت دار مثل همون مولفه همبندی تو گراف معمولیه؟ و مولفه قویا همبند چیه؟

مولفه های همبند که با گراف معمولی فرقی ندارند. تعریف رسمی مولفه های همبند و قویا همبند تو یه گراف جهتدار این طوریه:
u و v در یک مولفه ی همبندی هستند اگر با در نظر نگرفتن جهتها و تبدیل به گراف بی جهت در یک مولفه ی همبندی باشند.
u و v در یک مولفه ی قویا همبند هستند هر گاه هم از u به v یک مسیر جهتدار وجود داشته باشد هم از v به u.

 

[Goharshady1]

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

duplicate edges
ans<--0
for each vertex u in V
{
if u is unmarked
   {   
   ans<--ans+1   
   DFS(u)   
   }   
}
print(ans)

حالا الگوریتم قویا همبند رو شما بگین