در این مطلب، ویدئو Peaks در Python و C++ Codility Solutions درس 10 با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:17:44
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,160 –> 00:00:01,920
سلام به همه و به یک
2
00:00:01,920 –> 00:00:04,240
ویدیوی دیگر خوش آمدید راه حل امروز به نوعی
3
00:00:04,240 –> 00:00:06,080
چالش برانگیز است و من مجبور شدم دو الگوریتم مختلف را امتحان کنم
4
00:00:06,080 –> 00:00:08,080
زیرا الگوریتمی که با آن
5
00:00:08,080 –> 00:00:10,080
شروع کردم برای c plus plus کاملاً خوب کار
6
00:00:10,080 –> 00:00:12,160
می کرد اما
7
00:00:12,160 –> 00:00:14,639
وقتی با پایتون و پایتون نوشته می شد نمره کاملی نداشت. من
8
00:00:14,639 –> 00:00:16,239
هنوز نتوانستم
9
00:00:16,239 –> 00:00:18,160
تفاوت بین هر دو زبان را پیدا کنم، بنابراین
10
00:00:18,160 –> 00:00:20,240
شاید اگر شما مشتاق چالش اشکال زدایی
11
00:00:20,240 –> 00:00:22,560
هستید، ممکن است کمک کنید و
12
00:00:22,560 –> 00:00:24,640
در بخش نظرات برای ما پیام بگذارید، بنابراین
13
00:00:24,640 –> 00:00:26,240
به هر حال برای پایتون،
14
00:00:26,240 –> 00:00:28,000
الگوریتم دیگری را ارائه خواهیم کرد که ظاهرا
15
00:00:28,000 –> 00:00:30,080
کارآمدتر است. بنابراین ما میتوانیم
16
00:00:30,080 –> 00:00:32,479
با استفاده از هر دو زبان صد در صد امتیاز کسب کنیم،
17
00:00:32,479 –> 00:00:34,800
مجموعهای از ارتفاعات در یک
18
00:00:34,800 –> 00:00:36,640
زمین خاص به ما داده میشود و درست مانند
19
00:00:36,640 –> 00:00:39,120
ویدیوی قبلی که مشکل پرچمها را حل میکند
20
00:00:39,120 –> 00:00:41,520
، زمانی که عددی بالاتر از هر دو همسایهاش داریم، یک قله را تعریف میکنیم.
21
00:00:41,520 –> 00:00:43,920
22
00:00:43,920 –> 00:00:46,320
عدد چهار در اینجا بزرگتر
23
00:00:46,320 –> 00:00:48,640
از سه است و از عدد زیر نیز بزرگتر است
24
00:00:48,640 –> 00:00:50,719
که آن نیز سه است، بنابراین
25
00:00:50,719 –> 00:00:52,719
آن را به عنوان یک قله تعریف می کنیم سپس
26
00:00:52,719 –> 00:00:54,800
اوج دیگری داریم این عدد او re four
27
00:00:54,800 –> 00:00:56,559
بزرگتر از سه و بزرگتر از
28
00:00:56,559 –> 00:00:59,359
یک است، بنابراین ما یک قله دوم داریم و در
29
00:00:59,359 –> 00:01:01,840
کل سه قله در
30
00:01:01,840 –> 00:01:04,319
این آرایه نشان داده شده است و اگر این آرایه ما باشد و
31
00:01:04,319 –> 00:01:06,479
اینها قله های نسبی هستند، می خواهیم
32
00:01:06,479 –> 00:01:09,439
آرایه را به بلوک های برش تقسیم کنیم.
33
00:01:09,439 –> 00:01:11,280
حاوی
34
00:01:11,280 –> 00:01:14,240
تعداد یکسانی از عناصر، هر بلوک یا برش
35
00:01:14,240 –> 00:01:16,640
باید حداقل یک قله داشته باشد، بنابراین
36
00:01:16,640 –> 00:01:20,320
هدف یافتن حداکثر تعداد
37
00:01:20,320 –> 00:01:23,040
بلوک ها یا برش هایی از آرایه است
38
00:01:23,040 –> 00:01:25,840
که آرایه a را می توان به آنها تقسیم کرد، به یاد داشته باشید که
39
00:01:25,840 –> 00:01:28,159
ما حداقل به یک قله برای هر بلوک نیاز داریم. یا
40
00:01:28,159 –> 00:01:30,479
در هر برش و همه برش ها دارای
41
00:01:30,479 –> 00:01:32,560
تعداد عناصر یکسانی خواهند بود، بنابراین
42
00:01:32,560 –> 00:01:35,200
آرایه را به
43
00:01:35,200 –> 00:01:37,520
تعداد مساوی برش های عنصر
44
00:01:37,520 –> 00:01:40,320
تقسیم می کنیم، به عنوان مثال اگر این آرایه را به دو برش تقسیم کنیم، این
45
00:01:40,320 –> 00:01:43,119
یکی دو قله دارد، برش دیگر
46
00:01:43,119 –> 00:01:46,159
یک قله دارد، بنابراین این دو. برش ها نیز
47
00:01:46,159 –> 00:01:49,040
اندازه شش هستند که هر دو دارای شش عنصر هستند،
48
00:01:49,040 –> 00:01:51,439
سپس می توانیم آرایه را به
49
00:01:51,439 –> 00:01:53,840
سه برش مختلف با یک قله
50
00:01:53,840 –> 00:01:56,159
با طول یکسان یا سه
51
00:01:56,159 –> 00:01:58,159
برش تقسیم کنیم و در اینجا ما یک پیکربندی معتبر داریم.
52
00:01:58,159 –> 00:02:00,719
همه چیز راضی است،
53
00:02:00,719 –> 00:02:02,880
سپس تلاش می کنیم تا به حداکثر
54
00:02:02,880 –> 00:02:05,280
تعداد برش ها برسیم همانطور که با مشکل توضیح داده شده است، ما
55
00:02:05,280 –> 00:02:07,360
سعی می کنیم آرایه را به چهار
56
00:02:07,360 –> 00:02:10,160
برش مختلف از سه عنصر تقسیم
57
00:02:10,160 –> 00:02:13,120
کنیم که هر کدام دو برش داریم که با
58
00:02:13,120 –> 00:02:15,040
قله ها نیستند و هیچ قله ای ندارند زیرا
59
00:02:15,040 –> 00:02:17,840
ما هستیم. تمام
60
00:02:17,840 –> 00:02:20,160
شرایط مشکل را برآورده نمی کند این پیکربندی یک پیکربندی
61
00:02:20,160 –> 00:02:22,959
معتبر نیست و ما باید
62
00:02:22,959 –> 00:02:24,800
حداکثر تعداد برش هایی را که پیدا کرده ایم با
63
00:02:24,800 –> 00:02:27,599
رعایت شرایط که
64
00:02:27,599 –> 00:02:30,800
3 است برگردانیم. بنابراین این نتیجه بازگشتی ما است که
65
00:02:30,800 –> 00:02:33,200
توسط تابع ما ارائه می شود و بنابراین نتیجه تابع ما
66
00:02:33,200 –> 00:02:34,959
باید 3 باشد که
67
00:02:34,959 –> 00:02:36,959
حداکثر تعداد برش هایی است که
68
00:02:36,959 –> 00:02:39,280
می توانیم آرایه را با حداقل یک
69
00:02:39,280 –> 00:02:41,280
قله در هر برش به آن تقسیم کنیم، بنابراین اولین
70
00:02:41,280 –> 00:02:43,120
الگوریتمی که در اینجا ارائه می دهم به
71
00:02:43,120 –> 00:02:45,440
شرح زیر است و می خواهم یک آرایه p را در حالت ایستاده تعریف کنم.
72
00:02:45,440 –> 00:02:48,319
برای قلههایی با
73
00:02:48,319 –> 00:02:50,800
اندازه آرایه a یکسان و تمام
74
00:02:50,800 –> 00:02:53,680
عناصر این بردار p را در
75
00:02:53,680 –> 00:02:55,519
موقعیتهایی که پیکهایی داریم، مقداردهی اولیه میکنیم،
76
00:02:55,519 –> 00:02:57,680
میخواهیم یک را بگذاریم، بنابراین
77
00:02:57,680 –> 00:03:00,480
posi را مشخص میکنیم. سپس
78
00:03:00,480 –> 00:03:03,040
سعی میکنم حداکثر تعداد
79
00:03:03,040 –> 00:03:05,280
برشها را جستجو کنم، من میخواهم با
80
00:03:05,280 –> 00:03:08,000
تقسیم آرایه به تعدادی برش
81
00:03:08,000 –> 00:03:10,560
که برابر با تعداد پیکها است، شروع کنم، بنابراین
82
00:03:10,560 –> 00:03:12,879
تعداد برشها در اینجا برابر با k است، بنابراین
83
00:03:12,879 –> 00:03:15,760
این متغیر من و
84
00:03:15,760 –> 00:03:18,400
از مجموع p به معنای
85
00:03:18,400 –> 00:03:20,640
مجموع تعداد پیک
86
00:03:20,640 –> 00:03:23,840
ها به دو برش تغییر می کند، چرا با
87
00:03:23,840 –> 00:03:25,519
حداکثر تعداد پیک ها شروع می کنم زیرا از
88
00:03:25,519 –> 00:03:28,159
نظر تئوری اگر به یک پیک در هر برش نیاز داشته باشم
89
00:03:28,159 –> 00:03:30,799
در بهترین حالت می توانم به
90
00:03:30,799 –> 00:03:32,879
تعدادی برش مساوی با
91
00:03:32,879 –> 00:03:35,519
تعداد پیک ها برسیم، اما اگر این
92
00:03:35,519 –> 00:03:37,760
تعداد برش کار نکند، نمی
93
00:03:37,760 –> 00:03:39,599
توانیم پیکربندی را پیدا کنیم که تمام
94
00:03:39,599 –> 00:03:41,599
شرایط مسئله را برآورده کند، می توانیم
95
00:03:41,599 –> 00:03:44,879
k تعداد برش ها را یک بار کاهش
96
00:03:44,879 –> 00:03:47,280
دهیم و دوباره تلاش می کنیم. تا زمانی که پیکربندی را پیدا کنیم
97
00:03:47,280 –> 00:03:49,280
که با
98
00:03:49,280 –> 00:03:51,760
حداکثر تعداد k کار می کند و
99
00:03:51,760 –> 00:03:53,599
ملاحظاتی را باید در نظر بگیریم، به
100
00:03:53,599 –> 00:03:56,319
عنوان مثال اندازه مدول آرایه k
101
00:03:56,319 –> 00:03:57,840
باید برابر با صفر باشد، به این معنی که شما
102
00:03:57,840 –> 00:04:01,280
باید بتوانید آرایه را بر k
103
00:04:01,280 –> 00:04:04,319
عدد o تقسیم کنید. f برش میدهد، بنابراین اگر اینطور نیست،
104
00:04:04,319 –> 00:04:06,720
برشهایی با اندازه یکسان
105
00:04:06,720 –> 00:04:09,120
106
00:04:09,120 –> 00:04:10,720
داریم، بلافاصله به کاهش k میپریم، مجبور نیستیم
107
00:04:10,720 –> 00:04:12,720
الگوریتم خود را ادامه دهیم و روشی که میخواهم
108
00:04:12,720 –> 00:04:15,439
بررسی کنم آیا هر برش حداقل
109
00:04:15,439 –> 00:04:18,079
یک پیک دارد یا خیر، این است که با اعلام یک متغیر جدید
110
00:04:18,079 –> 00:04:20,399
double s متغیر ابتدا روی
111
00:04:20,399 –> 00:04:22,720
صفر است، اما وقتی پیک را در بردار p تشخیص می دهیم،
112
00:04:22,720 –> 00:04:23,680
113
00:04:23,680 –> 00:04:25,919
اگر به
114
00:04:25,919 –> 00:04:28,720
115
00:04:28,720 –> 00:04:31,120
انتهای یک برش برسیم، دو برابر s برابر با صفر داریم، تعداد s را یک افزایش می
116
00:04:31,120 –> 00:04:33,440
دهیم. این بدان معناست که ما به تازگی یک
117
00:04:33,440 –> 00:04:35,440
برش بدون پیک شناسایی کرده ایم، همچنین به این معنی است
118
00:04:35,440 –> 00:04:37,199
که پیکربندی فعلی ما که در حال
119
00:04:37,199 –> 00:04:39,199
آزمایش آن هستیم معتبر نیست، بنابراین
120
00:04:39,199 –> 00:04:42,160
ما از حلقه آزمایشی خود
121
00:04:42,160 –> 00:04:45,520
کاست و دوباره شروع می کنیم تا
122
00:04:45,520 –> 00:04:48,320
مقدار دو برابر s آزمایش شود.
123
00:04:48,320 –> 00:04:50,639
فقط در انتهای هر برش انجام شود و
124
00:04:50,639 –> 00:04:52,800
وقتی به انتهای آرایه
125
00:04:52,800 –> 00:04:55,759
رسیدیم و هیچ شرایط شکستی را ردیابی نکردیم
126
00:04:55,759 –> 00:04:58,080
به این معنی است که همه
127
00:04:58,080 –> 00:05:00,479
برش های ما حداقل دارای یک پیک هستند و
128
00:05:00,479 –> 00:05:02,639
سپس من می توانم k را برگردانم که
129
00:05:02,639 –> 00:05:05,360
حداکثر تعداد برش هایی که می توانم
130
00:05:05,360 –> 00:05:07,520
آرایه را به دو قسمت تقسیم کنید، حالا من به
131
00:05:07,520 –> 00:05:09,600
شما نشان می دهم که چگونه این را در c پلاس پلاس نوشتم و
132
00:05:09,600 –> 00:05:12,080
در پایتون چگونه در c به علاوه پلاس کار کرد
133
00:05:12,080 –> 00:05:14,240
اما در پایتون آنقدر زیاد نبود، بنابراین در پایتون امتیاز
134
00:05:14,240 –> 00:05:17,680
82 گرفتیم و بعد از آن می روم برای
135
00:05:17,680 –> 00:05:19,360
ارائه الگوریتم کارآمدتری به شما
136
00:05:19,360 –> 00:05:22,000
که نتایج ما را در پایتون بهبود میبخشد،
137
00:05:22,000 –> 00:05:24,080
بنابراین در c به علاوه این
138
00:05:24,080 –> 00:05:26,320
تابع راهحل ما است، یک
139
00:05:26,320 –> 00:05:28,240
پارامتر آرایه a را میگیرد، میخواهیم حالت لبه را آزمایش کنیم
140
00:05:28,240 –> 00:05:30,720
که اندازه a به
141
00:05:30,720 –> 00:05:33,120
شدت کمتر از سه در است. در این صورت
142
00:05:33,120 –> 00:05:35,280
ما هیچ پیکی نداریم، مجبور نیستیم چیزی را آزمایش
143
00:05:35,280 –> 00:05:37,360
کنیم، فقط فوراً صفر را
144
00:05:37,360 –> 00:05:39,360
برمیگردانیم، سپس
145
00:05:39,360 –> 00:05:42,320
بردار p را با همان اندازه یک
146
00:05:42,320 –> 00:05:44,800
مقدار اولیه در صفر برای همه
147
00:05:44,800 –> 00:05:47,919
عناصر ابتدا اعلام میکنیم و p را پر میکنیم. با
148
00:05:47,919 –> 00:05:51,280
یک هر زمان که یک قله در
149
00:05:51,280 –> 00:05:54,320
آرایه a را تشخیص دهیم، بنابراین اگر a i بزرگتر از i
150
00:05:54,320 –> 00:05:57,039
منهای یک باشد و در همان زمان a i
151
00:05:57,039 –> 00:05:59,280
بزرگتر از i به علاوه یک
152
00:05:59,280 –> 00:06:01,520
bi برابر با یک خواهد بود، من باید
153
00:06:01,520 –> 00:06:04,560
مقدار uh s را اعلام کنم. متغیر آن
154
00:06:04,560 –> 00:06:07,600
یک عدد صحیح با مجموع p
155
00:06:07,600 –> 00:06:09,919
عناصر آرایه p است شما می توانید یک حلقه for را
156
00:06:09,919 –> 00:06:12,800
در اینجا انجام دهید، من به سادگی از تابع انباشته
157
00:06:12,800 –> 00:06:15,199
استفاده می کنم، اما
158
00:06:15,199 –> 00:06:17,840
برای استفاده از این تابع باید کتابخانه عددی را وارد کنید، بنابراین
159
00:06:17,840 –> 00:06:20,560
اگر مجموع p برابر با صفر باشد به این معنی
160
00:06:20,560 –> 00:06:22,639
که هیچ پیکی نداریم، صفر را نیز برمی گردانیم،
161
00:06:22,639 –> 00:06:25,360
سپس حلقه for خود را شروع می کنیم. آزمایش
162
00:06:25,360 –> 00:06:27,440
برای حداکثر تعداد k حداکثر
163
00:06:27,440 –> 00:06:29,440
تعداد برشها را
164
00:06:29,440 –> 00:06:31,759
با k برابر با s شروع میکنیم که
165
00:06:31,759 –> 00:06:33,600
تعداد کل پیکهای آرایه a است و
166
00:06:33,600 –> 00:06:36,560
k را برای هر تکرار کاهش میدهیم، بنابراین اگر
167
00:06:36,560 –> 00:06:39,520
مدول اندازه نقطه k متفاوت باشد 0
168
00:06:39,520 –> 00:06:42,720
یعنی نمیتوانیم آرایه a را
169
00:06:42,720 –> 00:06:44,560
170
00:06:44,560 –> 00:06:46,800
با عدد k به برشهای مساوی تقسیم کنیم در این حالت باید
171
00:06:46,800 –> 00:06:49,440
k را یک واحد کاهش
172
00:06:49,440 –> 00:06:52,000
دهیم و دوباره شروع میکنیم اما اگر بتوانیم
173
00:06:52,000 –> 00:06:54,960
a را به برشهای مساوی تقسیم کنیم در این
174
00:06:54,960 –> 00:06:56,639
حالت میرویم برای انجام این کار در اینجا یک
175
00:06:56,639 –> 00:06:59,360
عدد صحیح n است به این معنی که تعداد عناصر
176
00:06:59,360 –> 00:07:01,919
در هر برش برابر است با اندازه نقطه
177
00:07:01,919 –> 00:07:04,000
تقسیم بر k و من دو عدد صحیح را تعریف می کنم که
178
00:07:04,000 –> 00:07:06,880
دو عدد s برابر با صفر و
179
00:07:06,880 –> 00:07:09,680
i برابر با صفر است، بنابراین اکنون می توانیم آن را
180
00:07:09,680 –> 00:07:12,560
اسکن کنیم. عناصر آرایه p از i
181
00:07:12,560 –> 00:07:14,880
برابر با صفر تا p است اندازه نقطه
182
00:07:14,880 –> 00:07:17,759
، عناصر p را به s اضافه می کنیم، به
183
00:07:17,759 –> 00:07:20,160
عبارت دیگر، مجموع قله هایی است که
184
00:07:20,160 –> 00:07:22,479
185
00:07:22,479 –> 00:07:25,599
تا موقعیت i به یک موقعیت معین رسیده ایم و اگر i به اضافه 1 مدول
186
00:07:25,599 –> 00:07:28,080
n برابر با 0 باشد، به این معنی که اگر به تازگی
187
00:07:28,080 –> 00:07:30,800
به آن رسیده ایم. انتهای یک برش و در
188
00:07:30,800 –> 00:07:33,039
عین حال تعداد کل
189
00:07:33,039 –> 00:07:35,360
پیک ها در این برش کمتر از یک است که
190
00:07:35,360 –> 00:07:38,160
از این حلقه برای خارج می شویم و این
191
00:07:38,160 –> 00:07:40,560
ما را به چهار مورد قبلی برمی گرداند که در آن
192
00:07:40,560 –> 00:07:42,960
می توانیم k را کاهش دهیم و از نو شروع کنیم در
193
00:07:42,960 –> 00:07:45,520
غیر این صورت اگر ما در
194
00:07:45,520 –> 00:07:48,080
انتهای برش خود یک اوج داریم و در همان
195
00:07:48,080 –> 00:07:50,160
زمان پایان برش است، ما
196
00:07:50,160 –> 00:07:52,400
تعداد پیک ها را صفر می کنیم تا بتوانیم
197
00:07:52,400 –> 00:07:55,199
دوباره شروع به شمارش برای برش جدید
198
00:07:55,199 –> 00:07:57,199
تعداد پیک ها کنیم، سپس وقتی
199
00:07:57,199 –> 00:08:00,000
به عدد رسیدیم. انتهای آرایه p ما
200
00:08:00,000 –> 00:08:02,560
همه برش ها را آزمایش کرده ایم که آیا اوج دارند
201
00:08:02,560 –> 00:08:05,759
یا نه، می توانیم آزمایش کنیم که آیا i بزرگتر است یا
202
00:08:05,759 –> 00:08:08,800
برابر با یک نقطه برای یک k خاص
203
00:08:08,800 –> 00:08:11,360
آیا پیکربندی پیدا کردیم که بتوانیم
204
00:08:11,360 –> 00:08:14,080
بدون شکستن به انتهای p برسیم.
205
00:08:14,080 –> 00:08:15,919
به این معنی که همه برش ها
206
00:08:15,919 –> 00:08:18,479
حداقل حاوی یک پیک هستند t در این
207
00:08:18,479 –> 00:08:20,639
حالت ما می خواهیم این عدد
208
00:08:20,639 –> 00:08:23,120
k را برگردانیم که تعداد برش ها است،
209
00:08:23,120 –> 00:08:24,960
در غیر این صورت اگر همه
210
00:08:24,960 –> 00:08:28,000
تعداد برش های مجاز k را امتحان
211
00:08:28,000 –> 00:08:30,400
کرده باشیم و چیزی
212
00:08:30,400 –> 00:08:32,080
را که برنگشته
213
00:08:32,080 –> 00:08:35,440
ایم پیدا نکرده باشیم، هرگز به عدد نرسیده ایم. در انتهای
214
00:08:35,440 –> 00:08:37,760
بردار p ما یکی را برمی گردانیم که
215
00:08:37,760 –> 00:08:39,919
به این معنی است که ما فقط می توانیم آرایه
216
00:08:39,919 –> 00:08:42,159
را به یک تکه تقسیم کنی