در این مطلب، ویدئو حل مسئله پل Kأ¶nigsberg با پایتون | نظریه گراف با پایتون شماره 1 با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:32:01
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,960 –> 00:00:03,199
سلام، به بخش اول نظریه گراف
2
00:00:03,199 –> 00:00:04,400
با پایتون
3
00:00:04,400 –> 00:00:05,839
در ویدیوی امروز خوش آمدید، ما قصد داریم
4
00:00:05,839 –> 00:00:07,520
یک مسئله تاریخی
5
00:00:07,520 –> 00:00:09,440
به نام مشکل پل کونیگزبرگ را حل کنیم
6
00:00:09,440 –> 00:00:10,639
که در
7
00:00:10,639 –> 00:00:12,799
واقع ریشه های شاخه ای را که ما اکنون آن را
8
00:00:12,799 –> 00:00:14,799
نظریه گراف می نامیم، حل می کنیم، این مسئله برای یک ریاضیدان مطرح شد.
9
00:00:14,799 –> 00:00:16,720
در
10
00:00:16,720 –> 00:00:19,359
اوایل دهه 1700 لئونارد اویلر نام گرفت و او آن را رد کرد که
11
00:00:19,359 –> 00:00:21,199
حتی ریاضیات نیست و
12
00:00:21,199 –> 00:00:23,600
شایسته زمان خود به عنوان ریاضیدان
13
00:00:23,600 –> 00:00:25,439
نیست، اما بعداً مشکل
14
00:00:25,439 –> 00:00:27,519
را حل کرد و راه حل خود را به یک آکادمی ارائه کرد و
15
00:00:27,519 –> 00:00:29,039
مقاله ای در مورد آن منتشر کرد، بنابراین
16
00:00:29,039 –> 00:00:30,560
باید چیزی الهام بخش او باشد. برای
17
00:00:30,560 –> 00:00:31,920
حل آن، بیایید نگاهی به
18
00:00:31,920 –> 00:00:33,920
مشکل بیندازیم و چرا اویلر فکر کرد که
19
00:00:33,920 –> 00:00:35,360
حتی ارزش وقتش را ندارد،
20
00:00:35,360 –> 00:00:37,520
در اینجا نقشه ای از شهر کونیگزبرگ
21
00:00:37,520 –> 00:00:39,120
در حدود سال 1613
22
00:00:39,120 –> 00:00:41,040
حدود صد سال قبل از اینکه اویلر در
23
00:00:41,040 –> 00:00:42,239
مورد مشکلی
24
00:00:42,239 –> 00:00:44,480
که در جنوب دریای بالتیک قرار دارد شنیده شود.
25
00:00:44,480 –> 00:00:46,399
در رودخانه ای به نام پرگل و شما می توانید ببینید
26
00:00:46,399 –> 00:00:48,559
که رودخانه از شهر می گذرد در
27
00:00:48,559 –> 00:00:51,199
اینجا رودخانه اینجاست
28
00:00:51,199 –> 00:00:54,320
و مسیری را دنبال
29
00:00:55,440 –> 00:00:59,840
می کند که شهر
30
00:01:00,320 –> 00:01:03,520
را به چهار منطقه جداگانه تقسیم می کند. منطقه ای
31
00:01:03,520 –> 00:01:04,720
به نام
32
00:01:04,720 –> 00:01:08,080
منطقه ای به نام ناحیه b به نام c و ناحیه ای
33
00:01:08,080 –> 00:01:09,439
به نام d
34
00:01:09,439 –> 00:01:11,280
اگر کمی بزرگنمایی کنیم، می توانیم ببینیم
35
00:01:11,280 –> 00:01:12,880
که هفت
36
00:01:12,880 –> 00:01:14,400
پل روی رودخانه قرار گرفته و
37
00:01:14,400 –> 00:01:16,880
مناطق مختلف شهر را
38
00:01:16,880 –> 00:01:19,920
به هم متصل می کند، به عنوان مثال اینجا یکی اینجا
39
00:01:19,920 –> 00:01:23,280
یکی دیگر اینجاست پل سوم
40
00:01:23,280 –> 00:01:27,520
پل چهارم پل شش
41
00:01:27,520 –> 00:01:30,159
و پل هفت کونیگزبرگ
42
00:01:30,159 –> 00:01:32,320
شهری ثروتمند در دهه 1700 بود و
43
00:01:32,320 –> 00:01:33,759
تاجران ثروتمند زیادی در شهر زندگی می کردند
44
00:01:33,759 –> 00:01:34,320
که
45
00:01:34,320 –> 00:01:35,680
یکی از کارهایی که طبق گزارشات آنها
46
00:01:35,680 –> 00:01:37,759
دوست داشتند بعدازظهرهای یکشنبه انجام دهند،
47
00:01:37,759 –> 00:01:39,280
گردش در شهر
48
00:01:39,280 –> 00:01:41,040
و برخی از آنها بود. یکی از
49
00:01:41,040 –> 00:01:42,399
اهالی شهر پازلی به ذهنم رسید تا
50
00:01:42,399 –> 00:01:44,159
کمی سرگرم کننده به
51
00:01:44,159 –> 00:01:46,079
پیاده روی های یکشنبه
52
00:01:46,079 –> 00:01:48,240
53
00:01:48,240 –> 00:01:49,520
54
00:01:49,520 –> 00:01:51,840
55
00:01:51,840 –> 00:01:53,680
شان اضافه کند. اگر از
56
00:01:53,680 –> 00:01:58,560
اینجا شروع کنیم، میتوانیم با این پل
57
00:01:58,560 –> 00:02:01,759
برخورد کنیم
58
00:02:01,759 –> 00:02:04,000
و از این پل رد شویم، راه برگردیم و از این پل عبور
59
00:02:04,000 –> 00:02:06,840
کنیم و از شهر عبور کنیم و از این
60
00:02:06,840 –> 00:02:08,080
یکی
61
00:02:08,080 –> 00:02:11,200
بگذریم، سپس از این پل عبور کنیم و سپس گیر کردهایم.
62
00:02:11,200 –> 00:02:12,720
ما هنوز
63
00:02:12,720 –> 00:02:15,280
دو پل داریم که اکنون
64
00:02:15,280 –> 00:02:17,040
پس از تلاش های مکرر از آنها عبور نکردیم، هیچ کس در
65
00:02:17,040 –> 00:02:18,879
شهر نتوانست معما را حل کند یا
66
00:02:18,879 –> 00:02:21,360
ثابت کند که انجام این کار غیرممکن است
67
00:02:21,360 –> 00:02:24,480
در سال 1736، شهردار یک شهر همسایه
68
00:02:24,480 –> 00:02:25,440
به نام دانزیگ
69
00:02:25,440 –> 00:02:27,520
به اویلر نامه نوشت و این را ذکر کرد.
70
00:02:27,520 –> 00:02:29,200
مشکل به او گفت که این
71
00:02:29,200 –> 00:02:30,879
یک مثال برجسته از
72
00:02:30,879 –> 00:02:32,319
محاسبه موقعیت است
73
00:02:32,319 –> 00:02:34,400
که شایسته است اویلر نابغه بزرگ شما
74
00:02:34,400 –> 00:02:35,920
با کمی تکبر به نامه پاسخ داد
75
00:02:35,920 –> 00:02:37,120
و گفت
76
00:02:37,120 –> 00:02:38,800
این نوع راه حل
77
00:02:38,800 –> 00:02:40,400
ارتباط کمی با ریاضیات دارد
78
00:02:40,400 –> 00:02:42,480
من نمی دانم چرا شما از یک ریاضیدان انتظار دارید که
79
00:02:42,480 –> 00:02:44,239
آن را به جای
80
00:02:44,239 –> 00:02:46,480
هر کس دیگری تولید کند، زیرا راه حل تنها مبتنی بر
81
00:02:46,480 –> 00:02:47,280
عقل است
82
00:02:47,280 –> 00:02:49,440
و کشف آن به هیچ اصل ریاضی بستگی ندارد، به
83
00:02:49,440 –> 00:02:51,440
همین دلیل
84
00:02:51,440 –> 00:02:53,680
من نمی دانم چرا حتی سوالاتی که
85
00:02:53,680 –> 00:02:55,200
رابطه کمی با
86
00:02:55,200 –> 00:02:55,920
ریاضیات
87
00:02:55,920 –> 00:02:57,280
دارند سریعتر حل می شوند. توسط
88
00:02:57,280 –> 00:02:59,120
ریاضیدانان نسبت به دیگران در این
89
00:02:59,120 –> 00:03:00,560
میان، جناب بزرگوار،
90
00:03:00,560 –> 00:03:02,080
شما این سوال را به هندسه موقعیت اختصاص داده اید،
91
00:03:02,080 –> 00:03:04,319
اما من
92
00:03:04,319 –> 00:03:06,319
در مورد w بی اطلاع هستم. این رشته جدید شامل
93
00:03:06,319 –> 00:03:08,159
چه نوع مسائلی می شود و اینکه لایبنیتس انتظار دارد چه نوع مشکلاتی را
94
00:03:08,159 –> 00:03:10,560
به
95
00:03:10,560 –> 00:03:11,280
این شکل بیان کند،
96
00:03:11,280 –> 00:03:13,040
بنابراین چند چیز در اینجا در جریان است،
97
00:03:13,040 –> 00:03:15,120
اول می بینیم که اویلر این را منفجر
98
00:03:15,120 –> 00:03:15,440
99
00:03:15,440 –> 00:03:18,319
می کند که حتی شایسته خودش یا واقعاً
100
00:03:18,319 –> 00:03:20,159
هیچ ریاضیدانی نیست.
101
00:03:20,159 –> 00:03:22,800
آیا این ذکر یک حساب
102
00:03:22,800 –> 00:03:23,440
موقعیت
103
00:03:23,440 –> 00:03:25,840
یا هندسه موقعیت است اکنون این یک
104
00:03:25,840 –> 00:03:26,959
فرمول مجدد
105
00:03:26,959 –> 00:03:29,440
از هندسه کلاسیک است که توسط
106
00:03:29,440 –> 00:03:31,360
ریاضیدان فیلسوف
107
00:03:31,360 –> 00:03:32,159
گوتفرید لایپنیتز
108
00:03:32,159 –> 00:03:35,760
در اواسط تا اواخر دهه 1600 و اوایل 1700 پیشنهاد شده است
109
00:03:35,760 –> 00:03:37,519
و این همان لایبنیزی است که ممکن
110
00:03:37,519 –> 00:03:39,519
است شنیده باشید در یک نبرد بوده است. با توجه به اینکه نیوتن
111
00:03:39,519 –> 00:03:39,920
112
00:03:39,920 –> 00:03:41,920
اولین کسی بود که حساب دیفرانسیل و انتگرال را اختراع کرد،
113
00:03:41,920 –> 00:03:43,920
همچنین همان لایبنیتسی است که ولتر
114
00:03:43,920 –> 00:03:46,879
در داستانش به خاطر
115
00:03:46,879 –> 00:03:49,040
برداشتش از مسئله فلسفی
116
00:03:49,040 –> 00:03:52,239
شر مورد انتقاد قرار گرفت، اکنون لایبنیتس مجموعه عظیمی از
117
00:03:52,239 –> 00:03:52,640
آثار خود را
118
00:03:52,640 –> 00:03:55,120
در مورد آنچه او تحلیل
119
00:03:55,120 –> 00:03:57,200
موقعیت میخواند نوشت که هرگز منتشر نکرد. هر یک از آنها
120
00:03:57,200 –> 00:03:57,840
و این
121
00:03:57,840 –> 00:04:00,159
به چند دلیل بود که او
122
00:04:00,159 –> 00:04:01,840
123
00:04:01,840 –> 00:04:03,840
در مورد این ایده هندسه
124
00:04:03,840 –> 00:04:05,599
pos از معاصرانش مورد تمسخر قرار گرفت. و ثانیاً او هرگز
125
00:04:05,599 –> 00:04:06,319
نتوانست
126
00:04:06,319 –> 00:04:08,000
چیزی را
127
00:04:08,000 –> 00:04:10,000
که ارزش یا ارزشی
128
00:04:10,000 –> 00:04:11,040
از نظر نظریه
129
00:04:11,040 –> 00:04:13,120
130
00:04:13,120 –> 00:04:15,840
131
00:04:15,840 –> 00:04:17,680
132
00:04:17,680 –> 00:04:20,720
میدانست با موفقیت تولید کند. وابستگی به چیزهایی
133
00:04:20,720 –> 00:04:23,199
مانند فاصله یا اندازه گیری و به
134
00:04:23,199 –> 00:04:25,199
جای تمرکز بر چیزهایی مانند برابری
135
00:04:25,199 –> 00:04:27,440
، به جای تمرکز بر مواردی مانند
136
00:04:27,440 –> 00:04:28,320
همخوانی
137
00:04:28,320 –> 00:04:30,800
و شباهت اجسام در فضا، اکنون
138
00:04:30,800 –> 00:04:32,880
لایبنیتس در این مورد بسیار نوشته است
139
00:04:32,880 –> 00:04:34,639
و همانطور که گفتم هرگز هیچ یک
140
00:04:34,639 –> 00:04:36,080
از آنها را منتشر
141
00:04:36,080 –> 00:04:37,840
نکرده است. شهردار دانسیگ،
142
00:04:37,840 –> 00:04:39,440
آنها فقط میتوانستند از
143
00:04:39,440 –> 00:04:41,360
مکاتباتی که یا
144
00:04:41,360 –> 00:04:44,000
با خود لایبنیتس داشتند یا از شنیدههایی
145
00:04:44,000 –> 00:04:45,759
که با ریاضیدانان دیگر صحبت
146
00:04:45,759 –> 00:04:47,520
میکردند، این موضوع را بدانند، اکنون مشکل پل کونیگزبرگ
147
00:04:47,520 –> 00:04:49,440
به وضوح با اویلر گیر کرده است، زیرا
148
00:04:49,440 –> 00:04:51,040
خیلی دیر نشده بود که او
149
00:04:51,040 –> 00:04:52,880
واقعاً راهحلی را منتشر کرد. اولین
150
00:04:52,880 –> 00:04:54,720
مرجعی که باید به راه حل اویلر بپردازیم
151
00:04:54,720 –> 00:04:56,320
به نامه ای است که او به یک
152
00:04:56,320 –> 00:04:58,880
ریاضیدان ایتالیایی به نام جووانی مارینونی نوشت.
153
00:04:58,880 –> 00:05:00,639
و در این که او می گوید یک مشکل
154
00:05:00,639 –> 00:05:02,160
برای من در مورد جزیره ای در شهر
155
00:05:02,160 –> 00:05:03,840
کونیگزبرگ که توسط رودخانه ای
156
00:05:03,840 –> 00:05:05,600
که توسط هفت پل احاطه شده است مطرح شد و از من پرسیده شد که
157
00:05:05,600 –> 00:05:07,120
آیا کسی می تواند
158
00:05:07,120 –> 00:05:08,960
پل های جداگانه را در یک پیاده روی متصل به
159
00:05:08,960 –> 00:05:10,960
گونه ای طی کند که هر پل
160
00:05:10,960 –> 00:05:11,840
فقط یک بار به
161
00:05:11,840 –> 00:05:13,840
من اطلاع داده شد که تا به حال هیچ کس
162
00:05:13,840 –> 00:05:15,600
امکان انجام این کار را
163
00:05:15,600 –> 00:05:17,520
نشان نداده یا نشان داده است که غیرممکن است این
164
00:05:17,520 –> 00:05:18,400
سؤال تا این حد
165
00:05:18,400 –> 00:05:20,000
بیهوده باشد، اما به نظرم از
166
00:05:20,000 –> 00:05:22,400
نظر هندسه، جبر
167
00:05:22,400 –> 00:05:24,000
و حتی هنر شمارش، ارزش توجه
168
00:05:24,000 –> 00:05:25,759
را دارد. با توجه به این
169
00:05:25,759 –> 00:05:27,360
موضوع به ذهنم خطور کرد که آیا این
170
00:05:27,360 –> 00:05:29,199
به هندسه موقعیتی تعلق دارد
171
00:05:29,199 –> 00:05:31,280
که لایب نیتس زمانی بسیار آرزوی آن
172
00:05:31,280 –> 00:05:31,759
را داشت
173
00:05:31,759 –> 00:05:33,919
و در اینجا مثال دیگری از تکبر اویلر است
174
00:05:33,919 –> 00:05:35,840
که می گوید به
175
00:05:35,840 –> 00:05:36,240
ذهنش خطور کرد
176
00:05:36,240 –> 00:05:38,400
که شاید این به
177
00:05:38,400 –> 00:05:40,560
هندسه تعلق دارد. موقعیتی که لایبنیتس ذکر کرده بود،
178
00:05:40,560 –> 00:05:41,840
اما میدانیم
179
00:05:41,840 –> 00:05:44,000
که شهردار دانزیگ قبلاً به
180
00:05:44,000 –> 00:05:45,759
این محاسبه موقعیت
181
00:05:45,759 –> 00:05:47,840
کاشت آن بذر در ذهن اویلر اشاره کرده است.
182
00:05:47,840 –> 00:05:48,880
183
00:05:48,880 –> 00:05:50,960
که پس از مدتی تامل، به
184
00:05:50,960 –> 00:05:53,440
یک قانون ساده و در عین حال کاملاً تثبیت شده دست یافتم
185
00:05:53,440 –> 00:05:55,199
که با کمک آن می توان فوراً
186
00:05:55,199 –> 00:05:57,440
برای همه نمونه هایی از این نوع
187
00:05:57,440 –> 00:05:59,520
با هر تعداد پل و با هر
188
00:05:59,520 –> 00:06:01,440
ترتیبی تصمیم گرفت که آیا چنین سفر رفت
189
00:06:01,440 –> 00:06:04,479
و برگشتی در حال حاضر در مقاله اویلر با راه حل امکان پذیر است یا خیر.
190
00:06:04,479 –> 00:06:06,160
او در رابطه با این مشکل
191
00:06:06,160 –> 00:06:07,520
اشاره میکند که میتوانست
192
00:06:07,520 –> 00:06:09,360
با بررسی تمام
193
00:06:09,360 –> 00:06:10,000
194
00:06:10,000 –> 00:06:12,080
مسیرهای ممکن از طریق شهر به طور کامل آن را حل کند، او
195
00:06:12,080 –> 00:06:13,440
این کار را سخت رد میکند
196
00:06:13,440 –> 00:06:15,120
و همچنین اشاره میکند که این یک
197
00:06:15,120 –> 00:06:16,639
تکنیک غیرممکن
198
00:06:16,639 –> 00:06:19,120
برای پیکربندیهایی با تعداد زیادی
199
00:06:19,120 –> 00:06:21,360
پل است، اما مشکل اصلی ناشی
200
00:06:21,360 –> 00:06:23,280
از مردم شهر کونیگزبرگ
201
00:06:23,280 –> 00:06:25,520
با استانداردهای امروزی بسیار ساده هستند
202
00:06:25,520 –> 00:06:27,120
و شما می توانید از رایانه برای بررسی
203
00:06:27,120 –> 00:06:29,039
کامل همه چیز استفاده کنید، بنابراین قبل از اینکه بخواهیم
204
00:06:29,039 –> 00:06:29,759
به
205
00:06:29,759 –> 00:06:31,840
چگونگی حل این مشکل اویلر بپردازیم،
206
00:06:31,840 –> 00:06:33,440
بیایید نگاهی بیندازیم که چگونه می توانیم از
207
00:06:33,440 –> 00:06:34,000
پایتون
208
00:06:34,000 –> 00:06:35,440
برای حل این مشکل به سرعت برای ما استفاده
209
00:06:35,440 –> 00:06:37,759
کنیم. برای حل این مشکل
210
00:06:37,759 –> 00:06:39,440
با پایتون، اولین کاری که باید
211
00:06:39,440 –> 00:06:41,199
انجام دهیم این است که بفهمیم چگونه میخواهیم از آن استفاده کنیم.
212
00:06:41,199 –> 00:06:42,000
nt
213
00:06:42,000 –> 00:06:44,080
اکنون در شهر قدم می زند در
214
00:06:44,080 –> 00:06:45,360
سمت راست صفحه،
215
00:06:45,360 –> 00:06:48,080
من نموداری از کونیگزبرگ دارم
216
00:06:48,080 –> 00:06:49,840
که توسط اویلر در مقاله خود استفاده شده بود.
217
00:06:49,840 –> 00:06:52,800
218
00:06:52,800 –> 00:06:53,120
219
00:06:53,120 –> 00:06:54,800
220
00:06:54,800 –> 00:06:56,319
221
00:06:56,319 –> 00:06:58,720
قسمت هایی که شما
222
00:06:58,720 –> 00:06:59,520
رودخانه پل ها
223
00:06:59,520 –> 00:07:01,840
را دارید و مناطق مختلف
224
00:07:01,840 –> 00:07:03,039
شهر را دارید در
225
00:07:03,039 –> 00:07:05,039
اینجا مناطق زمین با
226
00:07:05,039 –> 00:07:06,080
حروف بزرگ
227
00:07:06,080 –> 00:07:09,520
a b c و d
228
00:07:09,520 –> 00:07:12,000
و پل ها با حروف کوچک
229
00:07:12,000 –> 00:07:13,599
230
00:07:13,599 –> 00:07:17,039
a b c d
231
00:07:17,039 –> 00:07:20,720
e f و g برچسب گذاری شده اند حالا اجازه دهید در شهر قدم بزنیم
232
00:07:20,720 –> 00:07:21,360
233
00:07:21,360 –> 00:07:23,599
و نشان دهیم که چگونه میتوانیم آن را بهعنوان یک
234
00:07:23,599 –> 00:07:24,880
رشته در پایتون نشان
235
00:07:24,880 –> 00:07:28,639
دهیم، ابتدا با مساحت زمین شروع
236
00:07:28,639 –> 00:07:31,680
237
00:07:31,680 –> 00:07:34,880
238
00:07:34,880 –> 00:07:38,080
239
00:07:38,080 –> 00:07:40,080
میکنیم.
240
00:07:40,080 –> 00:07:42,240
241
00:07:42,240 –> 00:07:46,319
c بزرگ
242
00:07:46,319 –> 00:07:50,639
و ابتدا از پل عبور می کند با حروف کوچک c
243
00:07:50,639 –> 00:07:53,759
که ما را به زمین a هدایت می کند،
244
00:07:53,759 –> 00:07:56,800
سپس از پل کوچک a عبور
245
00:07:56,800 –> 00:07:57,759
می کنیم که ما را به
246
00:07:57,759 –> 00:08:01,199
منطقه b می برد سپس از پل عبور می کنیم و با حروف کوچک b عبور
247
00:08:01,199 –> 00:08:01,520
248
00:08:01,520 –> 00:08:04,720
می کنیم که ما را در یک پل کوچک قرار می دهد.
249
00:08:04,720 –> 00:08:08,160
d دوباره به ناحیه c برمی گردیم، سپس از
250
00:08:08,160 –> 00:08:08,639
پل با
251
00:08:08,639 –> 00:08:11,840
حروف کوچک g عبور می کنیم که ما را در ناحیه زمین d قرار می دهد
252
00:08:11,840 –> 00:08:13,199
و در نهایت از روی
253
00:08:13,199 –> 00:08:16,240
پل کوچک عبور می کنیم و ما را در
254
00:08:16,240 –> 00:08:18,400
ناحیه زمین a قرار می دهیم، بنابراین این یک
255
00:08:18,400 –> 00:08:19,440
نمایش
256
00:08:19,440 –> 00:08:22,400
از راه رفتن به عنوان یک رشته پایتون به ما می دهد و به این صورت
257
00:08:22,400 –> 00:08:23,919
است که می خواهیم پیاده روی ها را
258
00:08:23,919 –> 00:08:26,960
در برنامه خود نشان دهیم تا این کار را انجام دهیم،
259
00:08:26,960 –> 00:08:27,840
260
00:08:27,840 –> 00:08:31,360
ابتدا لیستی از پل ها را تعریف می کنیم،
261
00:08:31,360 –> 00:08:33,440
اکنون پل های موجود در
262
00:08:33,440 –> 00:08:34,640
نمودار با
263
00:08:34,640 –> 00:08:37,279
حروف کوچک نشان داده شده اند، اما این مفید است که
264
00:08:37,279 –> 00:08:37,760
بدانیم
265
00:08:37,760 –> 00:08:40,159
کدام منطقه زمین است. bridge با شروع پل شروع می شود
266
00:08:40,159 –> 00:08:41,360
و به پایان می رسد
267
00:08:41,360 –> 00:08:44,320
و انتخاب اینکه کدام ناحیه
268
00:08:44,320 –> 00:08:45,120
شروع پل
269
00:08:45,120 –> 00:08:47,120
و کدام ناحیه انتهای
270
00:08:47,120 –> 00:08:48,560
پل باشد واقعاً مهم نیست
271
00:08:48,560 –> 00:08:50,320
بنابراین ما هر پل را به عنوان یک
272
00:08:50,320 –> 00:08:51,839
رشته با سه کاراکتر نشان می دهیم
273
00:08:51,839 –> 00:08:53,920
که حرف بزرگ آن است. مساحت زمینی
274
00:08:53,920 –> 00:08:55,200
که پل را شروع میکند، سپس
275
00:08:55,200 –> 00:08:56,959
حرف کوچک نشاندهنده پل
276
00:08:56,959 –> 00:08:58,160
و حرف بزرگ
277
00:08:58,160 –> 00:09:00,240
نشاندهنده انتهای پایانی
278
00:09:00,240 –> 00:09:01,440
پل است،
279
00:09:01,440 –> 00:09:04,399
بنابراین در اینجا ما یک حروف کوچک a
280
00:09:04,399 –> 00:09:05,600
بزرگ b داریم
281
00:09:05,600 –> 00:09:09,040
که در اینجا با حروف بزرگ با این پل مطابقت دارد.
282
00:09:09,040 –> 00:09:12,800
e a با حروف کوچک b بزرگ
283
00:09:12,800 –> 00:09:17,120
b این پل است و
284
00:09:20,800 –> 00:09:22,480
اکنون که هر هفت پل
285
00:09:22,480 –> 00:09:24,560
را به صورت رشته در لیست پایتون
286
00:09:24,560 –> 00:09:25,680
داریم می توانیم به راه خود ادامه دهیم.
287
00:09:25,680 –> 00:09:26,160
288
00:09:26,160 –> 00:09:28,959
289
00:09:28,959 –> 00:09:30,560
در اینجا برای پیدا کردن
290
00:09:30,560 –> 00:09:31,120
تابعی
291
00:09:31,120 –> 00:09:34,160
به نام get walks با شروع از این
292
00:09:34,160 –> 00:09:35,279
است که
293
00:09:35,279 –> 00:09:38,080
همه پیاده روی های ممکن را که از یک منطقه زمینی شروع می شود تولید
294
00:09:38,080 –> 00:09:38,959
295
00:09:38,959 –> 00:09:40,160
می کند، همچنین
296
00:09:40,160 –> 00:09:42,640
پل هایی را که
297
00:09:42,640 –> 00:09:43,839
قبلا در لیستی تعریف کرده
298
00:09:43,839 –> 00:09:46,480
بودیم به آن تابع منتقل می کنیم و از یک لیست استفاده می کنیم. پیگیری همه
299
00:09:46,480 –> 00:09:47,600
پیادهرویهای ممکن
300
00:09:47,600 –> 00:09:49,600
و تابعی به نام make walks
301
00:09:49,600 –> 00:09:51,680
که به صورت بازگشتی فراخوانی میکنیم تا
302
00:09:51,680 –> 00:09:52,080
303
00:09:52,080 –> 00:09:54,880
همه پیادهرویها را از منطقه ایجاد کنیم،
304
00:09:54,880 –> 00:09:56,640
کاری که این تابع میخواهد انجام دهد این
305
00:09:56,640 –> 00:09:59,839
است که یک منطقه اولیه و همه چیزهایی را
306
00:09:59,839 –> 00:10:01,600
که قبلاً داشتهایم بگیرد. تا آن
307
00:10:01,600 –> 00:10:02,000
نقطه
308
00:10:02,000 –> 00:10:04,160
و همچنین پل هایی که از آن عبور کرده اند و
309
00:10:04,160 –> 00:10:06,240
همه مسیرهای ممکن را ایجاد می کنند که
310
00:10:06,240 –> 00:10:06,800
از آن
311
00:10:06,800 –> 00:10:10,000
منطقه شروع می شود، بنابراین در ابتدا پیاده روی هیچکدام از آنها وجود ندارد
312
00:10:10,000 –> 00:10:11,839
زیرا ما جایی را پیاده نرفته ایم و
313
00:10:11,839 –> 00:10:13,200
اگر
314
00:10:13,200 –> 00:10:15,200
اینطور باشد، ما فقط با منطقه ای شروع می
315
00:10:15,200 –> 00:10:16,720
کنیم ea در اینجا یک رشته
316
00:10:16,720 –> 00:10:18,480
با حرف بزرگ برای یکی از
317
00:10:18,480 –> 00:10:19,920
چهار منطقه
318
00:10:19,920 –> 00:10:22,160
a b c یا d است و ما از اتصال کوتاه
319
00:10:22,160 –> 00:10:23,279
320
00:10:23,279 –> 00:10:25,839
عملگر یا در اینجا استفاده میکنیم تا اگر
321
00:10:25,839 –> 00:10:27,440
قبلاً رشتهای از
322
00:10:27,440 –> 00:10:29,200
همه چیزهایی را که پیادهروی کردهایم، پیادهروی کنیم. یا
323
00:10:29,200 –> 00:10:31,120
همان ناحیه رشته اولیه برای پل
324
00:10:31,120 –> 00:10:31,680
325
00:10:31,680 –> 00:10:33,760
هایی که قبلاً از آنها عبور کرده ایم، اگر قبلاً از چند پل عبور کرده باشیم، چندین پل
326
00:10:33,760 –> 00:10:35,440
327
00:10:35,440 –> 00:10:36,160
328
00:10:36,160 –> 00:10:37,440
خواهیم داشت که قبلاً از آنها عبور کرده ایم، آنها
329
00:10:37,440 –> 00:10:39,279
فقط سه رشته کاراکتر
330
00:10:39,279 –> 00:10:41,200
از لیست پل ها هستند یا شروع می کنیم. با
331
00:10:41,200 –> 00:10:42,800
یک تاپل خالی، اولین کاری که باید
332
00:10:42,800 –> 00:10:44,240
انجام دهیم این است که
333
00:10:44,240 –> 00:10:46,320
تمام پل های موجود را از جایی که
334
00:10:46,320 –> 00:10:48,480
ایستاده ایم دریافت کنیم، بنابراین در حال حاضر
335
00:10:48,480 –> 00:10:50,720
در ناحیه ای که به این تابع منتقل کرده
336
00:10:50,720 –> 00:10:51,519
337
00:10:51,519 –> 00:10:53,839
ایم ایستاده ایم، همه پل هایی را که
338
00:10:53,839 –> 00:10:54,800
339
00:10:54,800 –> 00:10:57,760
حاوی منطقه درست در پل، بنابراین اگر از
340
00:10:57,760 –> 00:10:58,399
341
00:10:58,399 –> 00:11:01,040
ناحیه a شروع می کنیم، به دنبال همه پل
342
00:11:01,040 –> 00:11:01,680
هایی هستیم که
343
00:11:01,680 –> 00:11:04,720
دارای سرستون a هستند، تا زمانی که از آن
344
00:11:04,720 –> 00:11:05,279
345
00:11:05,279 –> 00:11:07,200
پل رد نشده باشد، پس این
346
00:11:07,200 –> 00:11:08,959
لیستی از همه
347
00:11:08,959 –> 00:11:09,600
پل های موجود
348
00:11:09,600 –> 00:11:11,120
را به ما می دهد. این لیست را داریم که باید
349
00:11:11,120 –> 00:11:12,640
تعیین کنیم آیا
350
00:11:12,640 –> 00:11:14,480
پیاده روی ما به پایان رسیده است یا نه به عبارت دیگر
351
00:11:14,480 –> 00:11:16,240
آیا می توانیم به راه رفتن ادامه دهیم یا نه، این
352
00:11:16,240 –> 00:11:18,240
کار را با بررسی اینکه
353
00:11:18,240 –> 00:11:19,760
آیا چیزی در
354
00:11:19,760 –> 00:11:22,000
لیست پل های موجود ما وجود دارد یا خیر انجام می دهیم، بنابراین اگر این
355
00:11:22,000 –> 00:11:23,279
لیست خالی باشد به
356
00:11:23,279 –> 00:11:25,040
این معنی است که ما گیر کرده ایم و
357
00:11:25,040 –> 00:11:26,640
به آن رسیده ایم. نقطهای که نمیتوانیم
358
00:11:26,640 –> 00:11:28,000
جلوتر برویم، دیگر
359
00:11:28,000 –> 00:11:30,160
هیچ پلی در دسترس ما نیست که بتوانیم از آن عبور
360
00:11:30,160 –> 00:11:31,839
کنیم، و ما میخواهیم
361
00:11:31,839 –> 00:11:33,920
رشته راهرفته را برداریم و آن را به فهرست پیادهرویهای خود اضافه کنیم،
362
00:11:33,920 –> 00:11:35,200
اکنون این
363
00:11:35,200 –> 00:11:37,680
رشته راهرفته شبیه آن
364
00:11:37,680 –> 00:11:39,600
نمایش رشتهای خواهد بود. پیادهروی که
365
00:11:39,600 –> 00:11:40,480
قبلاً دیدهایم،
366
00:11:40,480 –> 00:11:41,760
پس بیایید ببینیم چگونه میخواهیم بسازیم
367
00:11:41,760 –> 00:11:43,920
که برای هر پل در فهرست پلهای موجود،
368
00:11:43,920 –> 00:11:44,880
369
00:11:44,880 –> 00:11:47,440
چیزی را ایجاد میکنیم که من آن را گذرگاه مینامیم
370
00:11:47,440 –> 00:11:48,240
371
00:11:48,240 –> 00:11:51,440
و این نمایش رشتهای از پلی است که اکنون از
372
00:11:51,440 –> 00:11:54,079
آن عبور میکنیم. و
373
00:11:54,079 –> 00:11:54,720
374
00:11:54,720 –> 00:11:57,200
مساحت زمینی که از آن عبور میکنیم، اگر
375
00:11:57,200 –> 00:11:58,079
376
00:11:58,079 –> 00:12:01,040
از ناحیه a با حروف کوچک شروع کنیم و از پل
377
00:12:01,040 –> 00:12:01,600
378
00:12:01,600 –> 00:12:05,040
a با حروف کوچک به ناحیه b عبور
379
00:12:05,040 –> 00:12:08,240
کنیم، رشتهای خواهیم داشت که به نظر
380
00:12:08,240 –> 00:12:11,600
میرسد با حروف کوچک a
381
00:12:11,600 –> 00:12:14,959
بزرگ b اکنون محل عبور است. آیا این قسمت درست است
382
00:12:14,959 –> 00:12:17,519
در اینجا اگر ناحیه ای که در حال حاضر
383
00:12:17,519 –> 00:12:18,959
روی آن بزرگ
384
00:12:18,959 –> 00:12:21,360
A است در ابتدای رشته پل
385
00:12:21,360 –> 00:12:23,519
باشد، پس تقاطع
386
00:12:23,519 –> 00:12:25,440
فقط دو کاراکتر آخر در رشته است،
387
00:12:25,440 –> 00:12:27,440
همه چیز به جز نویسه اول
388
00:12:27,440 –> 00:12:29,920
همان چیزی است که این برش در اینجا می گوید که
389
00:12:29,920 –> 00:12:31,519
به ما حروف کوچک می دهد. a
390
00:12:31,519 –> 00:12:33,760
و بزرگ b اگر از طرف دیگر
391
00:12:33,760 –> 00:12:35,519
چیزی مانند این
392
00:12:35,519 –> 00:12:38,399
بزرگ b با حروف کوچک a بزرگ داشته باشیم،
393
00:12:38,399 –> 00:12:39,519
394
00:12:39,519 –> 00:12:41,600
از ناحیه a شروع می کنیم و از پل
395
00:12:41,600 –> 00:12:44,079
a با حروف کوچک به منطقه b عبور می کنیم،
396
00:12:44,079 –> 00:12:46,079
بنابراین آنچه ما نیاز داریم دو
397
00:12:46,079 –> 00:12:47,839
کاراکتر اول است. ما آنها را به ترتیب معکوس میخواهیم
398
00:12:47,839 –> 00:12:48,639
399
00:12:48,639 –> 00:12:50,320
و این همان کاری است که این برش در اینجا برای
400
00:12:50,320 –> 00:12:52,320
ما انجام میدهد، بنابراین پس از عبور
401
00:12:52,320 –> 00:12:54,240
ما میتوانیم تابع make walks را به
402
00:12:54,240 –> 00:12:55,440
صورت بازگشتی فراخوانی
403
00:12:55,440 –> 00:12:57,600
کنیم، میتوانیم ناحیه جدیدی را که
404
00:12:57,600 –> 00:12:59,360
از آن شروع میکنیم و
405
00:12:59,360 –> 00:12:59,920
آخرین
406
00:12:59,920 –> 00:13:02,399
کاراکتر است را به آن بدهیم. در رشته عبور
407
00:13:02,399 –> 00:13:03,040
408
00:13:03,040 –> 00:13:04,880
، رشته همه چیزهایی را که
409
00:13:04,880 –> 00:13:06,800
تا کنون طی
410
00:13:06,800 –> 00:13:09,680
کرده ایم، با برداشتن آنچه در حال حاضر داریم و به هم پیوستن
411
00:13:09,680 –> 00:13:11,040
آن با عبور خود،
412
00:13:11,040 –> 00:13:13,279
به روز می کنیم و با قرار دادن چندین پل
413
00:13:13,279 –> 00:13:14,560
که قبلاً از آنها عبور کرده ایم، به روز می کنیم.
414
00:13:14,560 –> 00:13:16,800
پلی که در ابتدا از آن عبور کردیم
415
00:13:16,800 –> 00:13:18,079
و
416
00:13:18,079 –> 00:13:19,760
هر چیزی که در
417
00:13:19,760 –> 00:13:21,600
پل های اصلی ما بود را از بسته بندی جدا
418
00:13:21,600 –> 00:13:23,760
می کنیم، اکنون که ما پیاده روی را تعریف کرده ایم، می
419
00:13:23,760 –> 00:13:26,399
توانیم آن را با منطقه اصلی که از آن
420
00:13:26,399 –> 00:13:29,839
عبور کرده ایم تا از آنجا شروع کنیم
421
00:13:29,839 –> 00:13:31,360
و سپس لیستی از آن ها را برگردانیم. بلوکهایی را که
422
00:13:31,360 –> 00:13:32,959
423
00:13:32,959 –> 00:13:37,519
اکنون برای یافتن همه راههای ممکن
424
00:13:37,519 –> 00:13:39,680
از هر چهار ناحیه ایجاد کردیم، میخواهیم
425
00:13:39,680 –> 00:13:41,440
فرهنگ لغتی به نام پیادهروی ایجاد کنیم که از آن
426
00:13:41,440 –> 00:13:43,519
شروع میشود و از
427
00:13:43,519 –> 00:13:46,320
درک فرهنگ لغت برای ساختن آن استفاده میکنیم که
428
00:13:46,320 –> 00:13:48,560
هر کلید یک منطقه خواهد بود
429
00:13:48,560 –> 00:13:49,360
از رشته
430
00:13:49,360 –> 00:13:52,720
a b c d بنابراین اولین کلید بزرگ
431
00:13:52,720 –> 00:13:52,959
432
00:13:52,959 –> 00:13:54,720
a خواهد بود، دومین کلید b بزرگ و غیره خواهد
433
00:13:54,720 –> 00:13:57,680
بود و مقادیر هر کلید
434
00:13:57,680 –> 00:13:58,320
435
00:13:58,320 –> 00:14:00,880
لیستی خواهد بود که دریافت می کنیم من git
436
00:14:00,880 –> 00:14:02,160
walk را
437
00:14:02,160 –> 00:14:04,240
از آن ناحیه خاص شروع می کنیم. ما
438
00:14:04,240 –> 00:14:05,199
آن دیکشنری را
439
00:14:05,199 –> 00:14:07,199
داریم که میتوانیم تعداد کل
440
00:14:07,199 –> 00:14:09,600
پیادهرویها را با استفاده از یک عبارت مولد در اینجا
441
00:14:09,600 –> 00:14:11,760
محاسبه کنیم که طول همه
442
00:14:11,760 –> 00:14:13,920
پیادهرویها را از تمام مقادیر مختلف در
443
00:14:13,920 –> 00:14:15,120
فرهنگ لغت محاسبه میکند، بنابراین من میخواهم
444
00:14:15,120 –> 00:14:17,680
به طول لیستی که
445
00:14:17,680 –> 00:14:19,519
از این دریافت پیاده روی به دست آوردیم با شروع از
446
00:14:19,519 –> 00:14:21,600
تابع، طول هر یک
447
00:14:21,600 –> 00:14:22,240
از آن ها را محاسبه کرده
448
00:14:22,240 –> 00:14:24,959
و سپس تمام طول
449
00:14:24,959 –> 00:14:26,639
ها را جمع آوری کنیم تا تعداد کل پیاده روی ها را به ما نشان دهیم
450
00:14:26,639 –> 00:14:28,320
و در نهایت می توانیم آن عدد را چاپ کنیم
451
00:14:28,320 –> 00:14:30,320
تا ببینیم تعداد کل پیاده روی ها چقدر است. وجود
452
00:14:30,320 –> 00:14:33,399
دارد و در این مورد میبینیم که 372 پیادهروی وجود دارد
453
00:14:33,399 –> 00:14:35,680
454
00:14:35,680 –> 00:14:37,920
و میتوانیم نگاهی به برخی از آنهایی
455
00:14:37,920 –> 00:14:38,959
بیندازیم که میتوانستیم
456
00:14:38,959 –> 00:14:42,079
از a شروع کنیم و اجازه دهید فقط
457
00:14:42,079 –> 00:14:43,519
به
458
00:14:43,519 –> 00:14:46,800
سه مورد اول نگاهی بیندازیم که پیادهرویها
459
00:14:46,800 –> 00:14:48,880
را به این شکل میبینیم که از خشکی شروع میکنیم.
460
00:14:48,880 –> 00:14:50,160
ناحیه یک
461
00:14:50,160 –> 00:14:52,560
پل متقاطع مورد پایین a به b سپس از پل عبور از صفحه
462
00:14:52,560 –> 00:14:53,600
پایین b
463
00:14:53,600 –> 00:14:56,560
سپس به ناحیه زمین پل متقاطع c
464
00:14:56,560 –> 00:14:58,079
به زمین c
465
00:14:58,079 –> 00:15:01,279
سپس پل d به یک پل e به d
466
00:15:01,279 –> 00:15:03,920
و پل f به b اکنون از
467
00:15:03,920 –> 00:15:05,199
پل های a
468
00:15:05,199 –> 00:15:08,480
b c d
469
00:15:08,480 –> 00:15:12,000
e و f استفاده کرده ایم. که شش پل است که ما
470
00:15:12,000 –> 00:15:14,480
از پل استفاده نکردهایم. این پیادهروی قادر
471
00:15:14,480 –> 00:15:16,880
به عبور از همه پلها دقیقاً یک بار نبود،
472
00:15:16,880 –> 00:15:20,240
بنابراین اکنون که 372
473
00:15:20,240 –> 0