Page 74 - C112215

.دراد دوجو n * n نیتلا عبرم ، n دننام یعیبط ددع ره یارب میدید سلاک رد راک رد هچنآ هب هجوت اب
دیدج عبرم کی n , ... , 3 , 2 , 1 یور رب تشگیاج کی لامعا اب و میراد ریز لکش دننام نیتلا عبرم کی مینک ضرف لاح

ینوتس ای رطس رد تروص نیا ریغ رد اریز ،دوب دهاوخ نیتلا عبرم کی زین هدمآ تسد هب عبرم هک دید میهاوخ .میا هدروآ تسد هب
ای رطس رد هک دنک یم باجیا تشگیاج صاوخ هب هجوت اب عوضوم نیا هک تشاد دهاوخ دوجو یرارکت وضع دیدج عبرم زا

.تسا ضقانت رد نآ ندوب نیتلا عبرم اب نیا و دشاب هتشاد دوجو یرارکت وضع زین لوا عبرم زا ینوتس
ّ

3 4 1 2 1 → 3 4 1 3 2

2 1 4 3 2 → 2 2 3 1 4

1 2 3 4 3 → 4 3 2 4 1

4 3 2 1 4 → 1 1 4 2 3

.تسا هدش لصاح مود لودج 1 و 4 ،2 ،3 دادعا اب بیترت هب لوا لودج زا 4 و 3 ،2 ،1 دادعا ینیزگیاج اب

سلاک رد راک

عبرم یور زا اه تشگیاج زا کی ره یارب سپس .دییامن صخشم تشگیاج کی ریز نیتلا یاه عبرم زا کی ره یارب

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

1 2 3 2 1 4 3 1 3 5 4 2

2 3 1 4 3 2 1 5 4 2 1 3

3 1 2 3 4 1 2 2 1 3 5 4

1 2 3 4 3 5 4 2 1

4 2 1 3 5

دماعتم نیتلا عبرم ود

نیا زا ریظن یاه هیارد نداد رارق مه رانک زا هک یروط هب دنشاب هبترم مه نیتلا عبرم ود B و A دینک ضرف :فیرعت

تمس یاه مقر مامت هک تسا یمقر ود ددع کی یواح نآ هناخ ره هک دوش لصاح هبترم نامه زا یدیدج عبرم ،عبرم ود
ٔ
ود مییوگ تروص نیا رد .تسا )سکعرب ای و( B عبرم هب طوبرم تسار تمس یاه مقر مامت و A عبرم هب طوبرم پچ
.دنشاب هدشن رارکت دیدج عبرم یاه هناخ رد دوجوم یمقر ود دادعا زا کی چیه هاگره »دندماعتم« B و A نیتلا عبرم

64 )شرامش( تا ّ یبیکرت :موس لصف