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