در این مطلب، ویدئو جستجوی باینری در پایتون: نقطه ثابت را پیدا کنید با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,030 –> 00:00:01,469
در این ویدیو می خواهیم
2
00:00:01,469 –> 00:00:04,110
مشکل زیر را در پایتون حل کنیم، بنابراین
3
00:00:04,110 –> 00:00:07,290
یک آرایه یا لیستی از n عدد صحیح مجزا به ما داده می شود
4
00:00:07,290 –> 00:00:09,059
که همه به
5
00:00:09,059 –> 00:00:10,950
ترتیب صعودی مرتب شده اند و می خواهیم
6
00:00:10,950 –> 00:00:13,380
تابعی بنویسیم که یک نقطه ثابت را برمی گرداند.
7
00:00:13,380 –> 00:00:14,820
یک نقطه ثابت را در یک
8
00:00:14,820 –> 00:00:17,310
مقدار کمی در آرایه تعریف میکنیم و اگر
9
00:00:17,310 –> 00:00:19,050
نقطه ثابتی وجود نداشته باشد، ادامه میدهیم
10
00:00:19,050 –> 00:00:22,320
و هیچ یک را بر نمیگردانیم، بنابراین اینکه چگونه یک
11
00:00:22,320 –> 00:00:24,869
نقطه ثابت را یک نقطه ثابت در یک آرایه تعریف کنیم a
12
00:00:24,869 –> 00:00:28,529
یک شاخص است. که a از I برابر است با
13
00:00:28,529 –> 00:00:31,109
I پس بیایید کمی آن را باز کنیم
14
00:00:31,109 –> 00:00:32,880
بیایید به این مثال در اینجا
15
00:00:32,880 –> 00:00:36,300
این لیست نگاهی بیندازیم تا نقطه ثابت در این
16
00:00:36,300 –> 00:00:39,960
آرایه خاص یا لیست a 3 باشد و
17
00:00:39,960 –> 00:00:42,270
دلیل آن این است که عنصر
18
00:00:42,270 –> 00:00:46,469
داده 3 است. در این آرایه درست در شاخص 3 قرار دارد،
19
00:00:46,469 –> 00:00:51,480
بنابراین 0 1 2 3 مقدار با
20
00:00:51,480 –> 00:00:53,789
مقدار شاخصی که در آن قرار دارد مطابقت دارد، بنابراین
21
00:00:53,789 –> 00:00:55,559
مثال دیگری در اینجا وجود دارد که نقطه ثابت
22
00:00:55,559 –> 00:00:57,899
در این آرایه 0 است، زیرا
23
00:00:57,899 –> 00:01:00,989
این عنصر 0 در شاخص 0 قرار دارد
24
00:01:00,989 –> 00:01:04,319
. آرایه، بنابراین اجازه دهید
25
00:01:04,319 –> 00:01:07,560
آنچه را که می خواهیم در این مثال ها در اینجا پیدا کنیم، روشن کنیم
26
00:01:07,560 –> 00:01:09,570
27
00:01:09,570 –> 00:01:11,220
نقطه ثابت در این آرایه را دوباره لیست کرده ایم در اینجا 3 است زیرا
28
00:01:11,220 –> 00:01:13,200
عنصر سوم در این آرایه برابر
29
00:01:13,200 –> 00:01:15,479
با مقدار 3 است. نقطه ثابت در این
30
00:01:15,479 –> 00:01:17,670
آرایه این عنصر 0 برابر با 0 است
31
00:01:17,670 –> 00:01:20,220
و در این مثال نهایی در اینجا این لیست
32
00:01:20,220 –> 00:01:22,470
انجام می دهد. حاوی یک نقطه ثابت نیست،
33
00:01:22,470 –> 00:01:24,810
زیرا هیچ عنصری در این لیست
34
00:01:24,810 –> 00:01:27,360
با شاخصی که در آن قرار دارد
35
00:01:27,360 –> 00:01:29,640
برابر نیست، بنابراین این 0 نیست، 1 نیست، دو نیست،
36
00:01:29,640 –> 00:01:31,590
نه سه، چهار و در پنج نقطه ثابتی وجود ندارد،
37
00:01:31,590 –> 00:01:33,329
بنابراین خروجی مورد
38
00:01:33,329 –> 00:01:35,189
انتظار بازده مورد انتظار است. ارزش هیچ خواهد بود،
39
00:01:35,189 –> 00:01:37,920
بنابراین بیایید در
40
00:01:37,920 –> 00:01:40,040
ابتدا از یک روش ساده گام
41
00:01:40,040 –> 00:01:42,000
برداریم که بتوانیم این مشکل را با آن حل کنیم،
42
00:01:42,000 –> 00:01:44,820
بنابراین سادهلوحانهترین روشی که میتوانیم
43
00:01:44,820 –> 00:01:46,590
این مشکل را حل کنیم این است که فقط بتوانیم
44
00:01:46,590 –> 00:01:48,240
از هر یک از عناصر در هر زمان
45
00:01:48,240 –> 00:01:50,340
مشخصی عبور کنیم. آرایهای که بهعنوان ورودی به ما داده میشود،
46
00:01:50,340 –> 00:01:52,409
میتوانیم بررسی کنیم که آیا آن عنصر
47
00:01:52,409 –> 00:01:55,200
برابر با شاخص است یا نه، بنابراین میتوانیم در ابتدا
48
00:01:55,200 –> 00:01:56,460
از اینجا شروع کنیم و
49
00:01:56,460 –> 00:01:58,649
میتوانیم بگوییم این عنصری است که روی آن برابر
50
00:01:58,649 –> 00:02:00,689
با صفر هستیم، بدانیم که برابر است با منفی ده
51
00:02:00,689 –> 00:02:02,939
حرکت در این است یک برابر با منفی
52
00:02:02,939 –> 00:02:05,880
یک نه آن برابر با منفی پنج حرکت
53
00:02:05,880 –> 00:02:09,330
به سمت این عنصر برابر با دو نه
54
00:02:09,330 –> 00:02:11,489
برابر است با صفر حرکت در این
55
00:02:11,489 –> 00:02:13,890
عنصر سوم برابر با سه بله است
56
00:02:13,890 –> 00:02:15,270
ادامه دهید و آن را به عنوان نقطه ثابت برگردانید،
57
00:02:15,270 –> 00:02:17,190
بنابراین این یک نوع است
58
00:02:17,190 –> 00:02:19,560
رویکرد خطی کلی که میتوانیم اتخاذ کنیم و
59
00:02:19,560 –> 00:02:21,270
از آنجایی که الگوریتم بسیار سادهای
60
00:02:21,270 –> 00:02:22,770
است، بیایید ادامه دهیم و
61
00:02:22,770 –> 00:02:24,450
آن را کدگذاری کنیم و میتوانیم یک تحلیل بسیار مختصر
62
00:02:24,450 –> 00:02:27,270
از
63
00:02:27,270 –> 00:02:29,900
پیچیدگی آن رویکرد انجام دهیم، بنابراین این را پیدا میکنیم که
64
00:02:29,900 –> 00:02:33,570
نام دارد. نقاط ثابتی را پیدا کنید،
65
00:02:33,570 –> 00:02:35,760
آن را خطی می نامیم، زیرا در حال انجام
66
00:02:35,760 –> 00:02:37,770
تعداد خطی عملیات هستیم و
67
00:02:37,770 –> 00:02:40,620
یک لیست را می گیرد، بنابراین کاری که می توانیم انجام دهیم این است که بتوانیم
68
00:02:40,620 –> 00:02:42,540
تمام عناصر موجود در لیست ها را حلقه
69
00:02:42,540 –> 00:02:44,040
بزنیم تا بتوانیم برای I و بگوییم.
70
00:02:44,040 –> 00:02:46,800
طول محدوده a و سپس کاری که میتوانیم انجام دهیم این است
71
00:02:46,800 –> 00:02:50,820
که میتوانیم بگوییم اگر a از I برابر است با I، پس
72
00:02:50,820 –> 00:02:52,560
کاری که میتوانیم انجام دهیم این است که فقط میتوانیم a
73
00:02:52,560 –> 00:02:54,810
از I را برگردانیم تا نقطه ثابت را برگردانیم در
74
00:02:54,810 –> 00:02:56,640
غیر این صورت اگر کل را طی کنیم.
75
00:02:56,640 –> 00:02:58,650
لیست و ما چیزی پیدا نکردیم
76
00:02:58,650 –> 00:03:00,810
فقط می خواهیم هیچ کدام را برگردانیم زیرا
77
00:03:00,810 –> 00:03:03,930
هیچ نقطه ثابتی در آن لیست وجود ندارد، بنابراین یک
78
00:03:03,930 –> 00:03:07,739
تجزیه و تحلیل بسیار آسان از این الگوریتم این است
79
00:03:07,739 –> 00:03:11,459
که پیچیدگی زمانی مطمئنا خطی است
80
00:03:11,459 –> 00:03:13,230
زیرا ما
81
00:03:13,230 –> 00:03:16,080
در بدترین حالت تمام لیست
82
00:03:16,080 –> 00:03:17,910
را مرور خواهیم کرد، بنابراین اگر اندازه لیست
83
00:03:17,910 –> 00:03:20,340
برابر باشد اندازه n پس ما
84
00:03:20,340 –> 00:03:22,260
پیچیدگی زمانی را تجربه خواهیم کرد یک O بزرگ از
85
00:03:22,260 –> 00:03:25,709
n و پیچیدگی فضا در این مورد
86
00:03:25,709 –> 00:03:27,900
آنقدر بد نیست و فقط ثابت است زیرا
87
00:03:27,900 –> 00:03:29,579
ما هیچ کاری با هیچ
88
00:03:29,579 –> 00:03:31,290
ساختار داده کمکی یا چیزی
89
00:03:31,290 –> 00:03:33,150
شبیه به آن انجام نمی دهیم. فقط با استفاده از مقدار ثابتی
90
00:03:33,150 –> 00:03:36,510
از فضا، بنابراین اشکالی ندارد، بنابراین
91
00:03:36,510 –> 00:03:38,010
زمان خطی
92
00:03:38,010 –> 00:03:39,959
برای حل این مشکل در اختیار داریم و میتوانیم
93
00:03:39,959 –> 00:03:43,170
بهتر عمل کنیم و یکی از جنبههای این مشکل
94
00:03:43,170 –> 00:03:44,220
که در واقع از آن استفاده نمیکنیم
95
00:03:44,220 –> 00:03:46,620
، این واقعیت است. که آرایه هایی که
96
00:03:46,620 –> 00:03:48,570
داده شده و لیستی که به ما داده شده است
97
00:03:48,570 –> 00:03:50,370
به صورت مرتب شده است، بنابراین ما تضمین می کنیم که
98
00:03:50,370 –> 00:03:52,440
لیست هایی که به عنوان ورودی داده شده است
99
00:03:52,440 –> 00:03:54,810
مرتب می شوند و احتمالاً می توانید به
100
00:03:54,810 –> 00:03:56,489
نوعی اشاره کنید که این واقعیت که این ویدیو
101
00:03:56,489 –> 00:03:58,380
در جستجوی باینری ساکن است
102
00:03:58,380 –> 00:04:00,480
لیست پخشی که
103
00:04:00,480 –> 00:04:02,730
احتمالاً از جستجوی باینری به عنوان یک
104
00:04:02,730 –> 00:04:06,360
ایده کلیدی در حل این مشکل استفاده خواهیم کرد، بنابراین بیایید
105
00:04:06,360 –> 00:04:08,070
ادامه دهیم و به نمونه های خود نگاه کنیم
106
00:04:08,070 –> 00:04:09,810
و به این فکر کنیم که چگونه می توان
107
00:04:09,810 –> 00:04:12,030
جستجوی باینری را برای این نمونه ها اعمال کرد و ببینیم
108
00:04:12,030 –> 00:04:14,640
آیا می توانیم آن را تغییر دهیم. این ایده برای
109
00:04:14,640 –> 00:04:16,440
اینکه بفهمیم آیا
110
00:04:16,440 –> 00:04:18,839
به یک نقطه ثابت رسیدهایم یا نه، بنابراین بیایید
111
00:04:18,839 –> 00:04:20,728
به این مثال نگاهی بیندازیم،
112
00:04:20,728 –> 00:04:22,048
کاری که میخواهم انجام دهم این است که
113
00:04:22,048 –> 00:04:24,360
دقیقاً بالای این عناصر در نظرات قرار میدهم.
114
00:04:24,360 –> 00:04:26,580
شاخص هایی که در آنها قرار دارند، بنابراین من این کار
115
00:04:26,580 –> 00:04:27,230
را برای
116
00:04:27,230 –> 00:04:29,600
مثال اول و همچنین دوم در اینجا
117
00:04:29,600 –> 00:04:32,960
118
00:04:32,960 –> 00:04:35,240
انجام می دهم، بنابراین آنچه در اینجا داریم در جستجوی باینری است، کاری که معمولا انجام می دهیم این است که قبل از ما نقطه پایین،
119
00:04:35,240 –> 00:04:36,950
نقطه اوج و همچنین نقطه میانی را تعریف
120
00:04:36,950 –> 00:04:39,140
می کنیم. شروع به رفتن و
121
00:04:39,140 –> 00:04:41,090
جستجوی عنصر هدف خود کنید، بنابراین
122
00:04:41,090 –> 00:04:43,280
اولین عنصر در این مورد 10-
123
00:04:43,280 –> 00:04:45,500
آخرین عنصر این آرایه 7 است و در این
124
00:04:45,500 –> 00:04:47,390
مثال خاص نقطه میانی این
125
00:04:47,390 –> 00:04:50,240
عنصر است که 0 به همین ترتیب نقطه میانی است و
126
00:04:50,240 –> 00:04:53,840
این دقیقاً در اینجا 5 است، بنابراین ما می توانیم انجام دهیم این
127
00:04:53,840 –> 00:04:56,390
است که ما فقط می توانیم بررسی کنیم که آیا یا
128
00:04:56,390 –> 00:04:59,270
مقداری که در اینجا روی آن قرار داریم کمتر یا
129
00:04:59,270 –> 00:05:01,160
بیشتر از شاخصی است که در آن قرار
130
00:05:01,160 –> 00:05:04,580
دارد، بنابراین در صورتی که
131
00:05:04,580 –> 00:05:07,010
خود عنصر کمتر از شاخص باشد، می دانیم
132
00:05:07,010 –> 00:05:09,020
که هیچ راهی وجود ندارد که آن
133
00:05:09,020 –> 00:05:11,570
نقطه ثابت قبل از آن باشد. نقطه ثابت
134
00:05:11,570 –> 00:05:14,450
فقط می تواند بعد از آن قرار گیرد، به همین ترتیب
135
00:05:14,450 –> 00:05:17,210
اگر ما در اینجا در این عنصر در اینجا باشیم،
136
00:05:17,210 –> 00:05:19,960
شاخص کمتر از خود عنصر است،
137
00:05:19,960 –> 00:05:22,640
همچنین تنها راهی که می توانیم یک
138
00:05:22,640 –> 00:05:25,640
نقطه ثابت پیدا کنیم این است که اگر
139
00:05:25,640 –> 00:05:28,070
قسمت چپ این آرایه را بررسی کنیم، این است
140
00:05:28,070 –> 00:05:30,770
که چون دو چیز واقعاً یک
141
00:05:30,770 –> 00:05:32,420
چیز این است که می دانیم ورودی
142
00:05:32,420 –> 00:05:34,610
مرتب شده است به طوری که وقتی به سمت راست
143
00:05:34,610 –> 00:05:36,140
می رویم عناصر افزایش می یابند بنابراین
144
00:05:36,140 –> 00:05:37,550
هیچ راهی وجود ندارد که بتوانیم
145
00:05:37,550 –> 00:05:39,500
چیزی را پیدا کنیم که یک
146
00:05:39,500 –> 00:05:41,720
نقطه ثابت در نیمه سمت راست این مثال باشد.
147
00:05:41,720 –> 00:05:44,360
و نکته دیگری که ما
148
00:05:44,360 –> 00:05:46,220
واقعاً خیلی مشخص نکردیم این واقعیت است
149
00:05:46,220 –> 00:05:48,410
که اعداد صحیح متمایز هستند
150
00:05:48,410 –> 00:05:50,030
زیرا اگر من چنین کاری انجام دهم
151
00:05:50,030 –> 00:05:52,820
اگر تعدادی از این عناصر را
152
00:05:52,820 –> 00:05:55,130
با عدد 5 جایگزین کنم و فرض کنید
153
00:05:55,130 –> 00:05:58,100
یک عنصر دیگر اضافه کنم چه اتفاقی می افتد. به این آرا اگر این کار را انجام دهم،
154
00:05:58,100 –> 00:06:00,140
اساساً چه اتفاقی میافتد
155
00:06:00,140 –> 00:06:02,180
، تضمینی ندارم که هر چیزی در
156
00:06:02,180 –> 00:06:03,890
سمت راست نقطه میانی به
157
00:06:03,890 –> 00:06:05,630
شدت بزرگتر از عنصری باشد که روی
158
00:06:05,630 –> 00:06:07,850
آن هستیم و در نتیجه
159
00:06:07,850 –> 00:06:10,550
لزوم