در این مطلب، ویدئو تغییر سکه – LeetCode 322 – Python (باز گشتی و تکراری!) با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:23:08
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:01,450 –> 00:00:03,919
[تشویق حضار]
2
00:00:03,919 –> 00:00:06,480
سلام و خوش آمدید، امروز در حال انجام یک
3
00:00:06,480 –> 00:00:08,240
سوال از کد لو رفتن هستیم به نام تغییر سکه،
4
00:00:08,240 –> 00:00:10,719
این یک رسانه است، بیایید مستقیم
5
00:00:10,719 –> 00:00:12,639
وارد آن شویم، به
6
00:00:12,639 –> 00:00:15,040
شما یک عدد صحیح یا یک سکه
7
00:00:15,040 –> 00:00:16,400
نشان دهنده سکه های با ارزش های مختلف
8
00:00:16,400 –> 00:00:19,199
و یک مقدار صحیح
9
00:00:19,199 –> 00:00:21,359
نشان دهنده مقدار کل داده می شود.
10
00:00:21,359 –> 00:00:23,199
11
00:00:23,199 –> 00:00:25,279
اگر این
12
00:00:25,279 –> 00:00:26,960
مقدار پول با
13
00:00:26,960 –> 00:00:29,439
ترکیبی از سکههای بازده منفی قابل جبران نباشد، کمترین تعداد سکههایی را که نیاز
14
00:00:29,439 –> 00:00:30,560
15
00:00:30,560 –> 00:00:32,079
دارید برمیگرداند، ممکن است فرض کنید که تعداد بینهایتی
16
00:00:32,079 –> 00:00:34,880
از هر نوع سکه دارید.
17
00:00:34,880 –> 00:00:37,280
در اینجا به سکه های یک دو
18
00:00:37,280 –> 00:00:39,760
پنج و مقدار یازده داده می شود، ما خروجی
19
00:00:39,760 –> 00:00:42,879
سه می دهیم زیرا یک پنج را در دومی
20
00:00:42,879 –> 00:00:43,680
پنج
21
00:00:43,680 –> 00:00:45,840
و یک یک را می گیریم تا یازده شود
22
00:00:45,840 –> 00:00:47,280
و دوباره تعداد بی نهایت از
23
00:00:47,280 –> 00:00:49,760
هر سکه داریم بنابراین می توانیم از یک
24
00:00:49,760 –> 00:00:52,320
دو و پنج استفاده کنیم. ما می خواهیم به
25
00:00:52,320 –> 00:00:53,840
عنوان مثال دو
26
00:00:53,840 –> 00:00:56,559
سکه دو مقدار سه بدون مقدار دو
27
00:00:56,559 –> 00:00:58,079
تا سه جمع شود بنابراین ما
28
00:00:58,079 –> 00:01:00,079
منفی یک
29
00:01:00,079 –> 00:01:02,399
مثال سه سکه یک مقدار صفر را در
30
00:01:02,399 –> 00:01:05,119
اینجا برمی گردانیم منهای یک
31
00:01:05,119 –> 00:01:06,960
را برمی گردانیم زیرا برای اینکه مقدار
32
00:01:06,960 –> 00:01:09,360
صفر شود ما به صفر سکه نیاز داریم و می توانیم
33
00:01:09,360 –> 00:01:11,680
آن رقم را ایجاد کنیم و به همین دلیل است که
34
00:01:11,680 –> 00:01:13,280
صفر را به
35
00:01:13,280 –> 00:01:15,600
عنوان مثال چهار سکه یک مقدار یک برمی گردانیم،
36
00:01:15,600 –> 00:01:18,560
فقط باید از یک سکه از یک استفاده کنیم تا
37
00:01:18,560 –> 00:01:20,080
یک و پنج
38
00:01:20,080 –> 00:01:22,320
سکه یک مقدار دو استفاده
39
00:01:22,320 –> 00:01:25,040
کنیم تا به دو برسیم.
40
00:01:25,600 –> 00:01:27,759
اکنون این شبیه چیزی به نام
41
00:01:27,759 –> 00:01:30,720
مشکل کوله پشتی است که اساساً به این معنی است
42
00:01:30,720 –> 00:01:32,159
که هیچ
43
00:01:32,159 –> 00:01:33,920
میانبر یا ترفندی برای آن وجود ندارد، ما باید
44
00:01:33,920 –> 00:01:35,520
تمام ترکیبات مختلف را
45
00:01:35,520 –> 00:01:37,759
برای دریافت پاسخ خود پیدا کنیم
46
00:01:37,759 –> 00:01:39,840
و این به این دلیل است که ما نمی توانیم پیش بینی کنیم
47
00:01:39,840 –> 00:01:41,439
که چه سکه هایی قرار است استفاده شود. به
48
00:01:41,439 –> 00:01:43,600
عنوان مثال، در پاسخ نهایی
49
00:01:43,600 –> 00:01:45,439
ما نمی توانیم به گونه ای به آن نزدیک شویم و بگوییم سلام،
50
00:01:45,439 –> 00:01:47,360
بیایید سعی کنیم از بزرگترین سکه هایی
51
00:01:47,360 –> 00:01:50,240
که داریم استفاده کنیم و دیگر نمی توانیم از آنها استفاده کنیم، سکه های
52
00:01:50,240 –> 00:01:51,840
کوچکتر را امتحان کنیم،
53
00:01:51,840 –> 00:01:53,680
زیرا اگر
54
00:01:53,680 –> 00:01:54,399
55
00:01:54,399 –> 00:01:56,640
نمونه
56
00:01:56,640 –> 00:02:00,560
سکه های زیر را داشته باشیم 311 مقدار 21 چه می شود. برای استفاده از 11
57
00:02:00,560 –> 00:02:03,520
و اکنون مقدار باقیمانده ما 10 خواهد بود،
58
00:02:03,520 –> 00:02:05,280
اما نه سه و نه 11 نمی
59
00:02:05,280 –> 00:02:07,200
توانند ما را به 10 برسانند، بنابراین
60
00:02:07,200 –> 00:02:08,639
این رویکرد کارساز نخواهد بود، در واقع
61
00:02:08,639 –> 00:02:10,239
باید از هفت سکه از سه
62
00:02:10,239 –> 00:02:13,520
سکه برای رسیدن به 21 استفاده
63
00:02:13,520 –> 00:02:16,000
کنیم. چیزی که می توانیم انجام با این حال
64
00:02:16,000 –> 00:02:18,239
پیگیری است محاسبات قبلی ما و
65
00:02:18,239 –> 00:02:20,800
استفاده از آنها برای محاسبات آینده به این
66
00:02:20,800 –> 00:02:22,400
حافظه می گویند که می تواند از طریق
67
00:02:22,400 –> 00:02:24,400
برنامه نویسی پویا انجام شود، اما قبل از اینکه به
68
00:02:24,400 –> 00:02:27,280
طور تکراری آن را حل کنیم، اجازه دهید نگاهی کوتاه
69
00:02:27,280 –> 00:02:28,879
به روش دیگری بیندازیم، این را به
70
00:02:28,879 –> 00:02:30,879
صورت بازگشتی حل می کنیم و از بالا به پایین به آن نگاه می کنیم.
71
00:02:30,879 –> 00:02:32,879
به سرعت قبل از اینکه به
72
00:02:32,879 –> 00:02:35,680
راه حل تکراری خود برویم،
73
00:02:35,680 –> 00:02:37,440
بنابراین مانند همیشه اولین کاری که
74
00:02:37,440 –> 00:02:40,000
می خواهیم انجام دهیم این است که با یک مثال
75
00:02:40,000 –> 00:02:42,480
در اینجا شروع کنیم، من یک مثال دارم که در آن سکه ها
76
00:02:42,480 –> 00:02:45,440
یک دو پنج و مقدار آن
77
00:02:45,440 –> 00:02:46,959
شش است که حداقل تعداد سکه های
78
00:02:46,959 –> 00:02:48,840
مورد نیاز برای مقدار
79
00:02:48,840 –> 00:02:51,519
شش را خوب بسازید ما سکه های یک دو پنج را در
80
00:02:51,519 –> 00:02:53,360
اختیار داریم کاری که می خواهیم انجام دهیم این است
81
00:02:53,360 –> 00:02:54,959
که تمام راه های ساختن شش سکه از این
82
00:02:54,959 –> 00:02:56,879
سکه ها را امتحان کنیم و
83
00:02:56,879 –> 00:02:58,959
از روشی استفاده کنیم که کمترین تعداد سکه را استفاده می کند،
84
00:02:58,959 –> 00:03:00,480
85
00:03:00,480 –> 00:03:02,159
بنابراین ابتدا کاری که می توانیم انجام دهیم استفاده از قزل آلا است.
86
00:03:02,159 –> 00:03:04,560
سکه یک ما یک مانت شش داریم و از
87
00:03:04,560 –> 00:03:07,200
سکه یک استفاده می کنیم که مقدار پنج باقی می ماند،
88
00:03:07,200 –> 00:03:09,440
یعنی اگر حداقل تعداد
89
00:03:09,440 –> 00:03:12,560
سکه های مورد نیاز برای ساختن پنج عدد x
90
00:03:12,560 –> 00:03:16,000
باشد، x به علاوه یک طول می کشد تا شش بسازیم
91
00:03:16,000 –> 00:03:17,760
، حداکثر x به اضافه یک را می گیریم. سکه برای ساختن
92
00:03:17,760 –> 00:03:19,440
93
00:03:19,440 –> 00:03:21,920
حالا اگر سعی کنیم از سکه دو استفاده
94
00:03:21,920 –> 00:03:23,599
کنیم، مقدار چهار باقی میماند
95
00:03:23,599 –> 00:03:25,440
و اگر y حداقل تعداد سکههایی است
96
00:03:25,440 –> 00:03:27,040
که باید چهار بسازیم، حداکثر
97
00:03:27,040 –> 00:03:28,159
98
00:03:28,159 –> 00:03:31,760
y به اضافه یک سکه طول میکشد تا مقدار شش را به دست بیاوریم،
99
00:03:31,760 –> 00:03:34,000
فقط یک سکه طول میکشد. برای رفتن از چهار به
100
00:03:34,000 –> 00:03:36,159
شش فقط یک سکه طول می کشد تا از پنج
101
00:03:36,159 –> 00:03:37,440
به شش برسد
102
00:03:37,440 –> 00:03:39,440
و در اینجا در این تجسم، هر
103
00:03:39,440 –> 00:03:40,640
تفاوت سطح
104
00:03:40,640 –> 00:03:43,120
نشان دهنده یک سکه اضافی است که
105
00:03:43,120 –> 00:03:44,080
استفاده می شود
106
00:03:44,080 –> 00:03:46,879
در حالی که هر سکه با
107
00:03:46,879 –> 00:03:49,920
یک اسلش و ارزشی که دارد نشان داده می شود،
108
00:03:49,920 –> 00:03:51,680
بنابراین در اینجا ما استفاده می کنیم. یک سکه تکی با ارزش
109
00:03:51,680 –> 00:03:54,080
یک تک سکه ارزش دو
110
00:03:54,080 –> 00:03:57,840
ادامه دارد اگر از سکه 1.2 استفاده نکنیم
111
00:03:57,840 –> 00:04:00,879
مقدار باقیمانده
112
00:04:00,879 –> 00:04:02,159
ما یک خواهد بود
113
00:04:02,159 –> 00:04:04,799
و اگر z تعداد سکه های مورد نیاز
114
00:04:04,799 –> 00:04:06,959
برای ایجاد آن مقدار باشد
115
00:04:06,959 –> 00:04:10,480
حداکثر z به اضافه یک طول می کشد. برای ایجاد مقدار
116
00:04:10,480 –> 00:04:12,480
شش، از همه اینها درست از پنج
117
00:04:12,480 –> 00:04:14,560
چهار یک، فقط یک سکه اضافی طول
118
00:04:14,560 –> 00:04:17,120
می کشد تا به شش برسیم،
119
00:04:17,120 –> 00:04:19,040
فقط یک سکه بیشتر به ارزش یک دو
120
00:04:19,040 –> 00:04:20,160
یا پنج نیاز دارد،
121
00:04:20,160 –> 00:04:22,240
بنابراین اینجا چه کاری می خواهیم انجام دهیم، می خواهیم
122
00:04:22,240 –> 00:04:25,440
حداقل تعداد سکه ها را پیدا کنیم. برای ساخت r مورد نیاز است
123
00:04:25,440 –> 00:04:28,639
مقدار باقیمانده سکه های
124
00:04:28,639 –> 00:04:31,199
مورد نیاز برای ساختن 5 4 1.
125
00:04:31,199 –> 00:04:34,800
به طوری که x y z چیزی است که می خواهیم انجام دهیم این است
126
00:04:34,800 –> 00:04:38,720
که 6 برابر با حداقل x y z داشته باشیم
127
00:04:38,720 –> 00:04:40,800
و فقط 1 را به آن اضافه کنیم و به این ترتیب می
128
00:04:40,800 –> 00:04:42,320
دانیم که حداقل تعداد سکه های مورد نیاز
129
00:04:42,320 –> 00:04:44,160
برای ساختن 6 سکه وجود دارد،
130
00:04:44,160 –> 00:04:47,040
اما اکنون چگونه بفهمیم x y z چیست
131
00:04:47,040 –> 00:04:48,320
،
132
00:04:48,320 –> 00:04:49,840
می توانیم همان کار را انجام
133
00:04:49,840 –> 00:04:52,000
دهیم، فقط می توانیم از تمام سکه های روی هر یک از
134
00:04:52,000 –> 00:04:52,800
آنها استفاده
135
00:04:52,800 –> 00:04:54,880
کنیم و تا آخر حباب به بالا برویم
136
00:04:54,880 –> 00:04:57,840
و بفهمیم که شش چیست،
137
00:04:57,840 –> 00:04:59,680
اما با این کار ما کارهای زیادی انجام خواهیم داد
138
00:04:59,680 –> 00:05:01,520
. عملیات را تکرار کنید، بنابراین کاری
139
00:05:01,520 –> 00:05:03,520
که میخواهیم انجام دهیم این است که از کوچکترین سکهای
140
00:05:03,520 –> 00:05:06,479
که در اختیار داریم استفاده کنیم و پس از انجام آن تا جایی که میتوانیم به پایینتر
141
00:05:06,479 –> 00:05:08,479
برویم، سپس به سراغ
142
00:05:08,479 –> 00:05:11,039
سکههای بزرگتری مانند دو پنج
143
00:05:11,039 –> 00:05:12,160
میرویم، به این ترتیب، همه این
144
00:05:12,160 –> 00:05:13,919
محاسبات را در چیزی ذخیره میکنیم. یادداشت
145
00:05:13,919 –> 00:05:15,759
نامیده می شود، یک فرهنگ لغت است که
146
00:05:15,759 –> 00:05:17,360
مقادیر و حداقل تعداد سکه های
147
00:05:17,360 –> 00:05:19,520
مورد نیاز برای مقدار تعیین شده را در خود نگه می دارد
148
00:05:19,520 –> 00:05:21,039
و همانطور که به سکه های بزرگتر
149
00:05:21,039 –> 00:05:23,199
می رویم، فقط یادداشت را به روز می کنیم زیرا
150
00:05:23,199 –> 00:05:25,360
محاسبات کوچکتر ما کامل شده است،
151
00:05:25,360 –> 00:05:28,000
بنابراین بیایید همه این موارد را درست مرور کنیم.
152
00:05:28,000 –> 00:05:29,440
اولین کاری که انجام می دهیم ما یک کوه داریم
153
00:05:29,440 –> 00:05:31,280
ما با سکه یک شروع می کنیم، این
154
00:05:31,280 –> 00:05:32,639
کوچکترین سکه
155
00:05:32,639 –> 00:05:34,960
ما است، اکنون کوه پنج داریم،
156
00:05:34,960 –> 00:05:36,479
بنابراین دوباره این یک مشکل جدید است، ما
157
00:05:36,479 –> 00:05:38,560
مقدار پنج سکه داریم یک دو پنج می
158
00:05:38,560 –> 00:05:40,240
خواهیم از کوچکترین سکه ای که داریم نقطه
159
00:05:40,240 –> 00:05:42,479
یک یا مقدار چهار استفاده
160
00:05:42,479 –> 00:05:44,000
کنیم. کمترین تعداد سکههای
161
00:05:44,000 –> 00:05:45,520
مورد نیاز برای ساخت این مقدار، ما هیچ
162
00:05:45,520 –> 00:05:47,199
ایدهای نداریم، حتی نمیدانیم که آیا میتوانیم مقدار چهار را بسازیم یا نه،
163
00:05:47,199 –> 00:05:49,759
بنابراین به عنوان یک مکان نگهدار برای
164
00:05:49,759 –> 00:05:51,520
همه این مقادیر، میخواهیم بگوییم
165
00:05:51,520 –> 00:05:54,000
که حداقل تعداد سکههای مورد نیاز بینهایت طول میکشد.
166
00:05:54,000 –> 00:05:56,000
برای ایجاد این مقادیر و من
167
00:05:56,000 –> 00:05:57,759
توضیح خواهم داد که چرا ما از یک بی نهایت در
168
00:05:57,759 –> 00:05:59,680
کمی استفاده می
169
00:05:59,680 –> 00:06:02,479
کنیم، به هر حال ما در مقدار چهار هستیم، می خواهیم
170
00:06:02,479 –> 00:06:04,319
از کوچکترین سکه استفاده کنیم که سکه یک است،
171
00:06:04,319 –> 00:06:06,720
اکنون در حدود سه مقدار سه
172
00:06:06,720 –> 00:06:08,639
کوچکترین سکه هستیم که یک مقدار درست است.
173
00:06:08,639 –> 00:06:10,400
دو و میتوانید ببینید که چگونه
174
00:06:10,400 –> 00:06:12,479
پشته بازگشتی درست میشود، ما
175
00:06:12,479 –> 00:06:14,560
نمیتوانیم به سه برگردیم تا زمانی
176
00:06:14,560 –> 00:06:17,199
که تماس دو را
177
00:06:17,199 –> 00:06:19,280
به پایان برسانیم، بنابراین در دو با کوچکترین سکه
178
00:06:19,280 –> 00:06:21,120
در یک کوچکترین نقطه هستیم و در
179
00:06:21,120 –> 00:06:22,160
صفر هستیم.
180
00:06:22,160 –> 00:06:24,639
در مقدار صفر ما قبلاً این را دیده ایم
181
00:06:24,639 –> 00:06:27,680
صفر سکه برای صفر کردن،
182
00:06:27,680 –> 00:06:28,639
بنابراین
183
00:06:28,639 –> 00:06:30,080
این چیزی است که در واقع
184
00:06:30,080 –> 00:06:32,479
در یادداشت نیز ذخیره می شود.
185
00:06:32,479 –> 00:06:33,759
کلیدهای اینجا قرار است مقادیر را نشان
186
00:06:33,759 –> 00:06:35,199
187
00:06:35,199 –> 00:06:36,880
188
00:06:36,880 –> 00:06:39,039
189
00:06:39,039 –> 00:06:41,039
دهند. ما
190
00:06:41,039 –> 00:06:42,000
می دانیم
191
00:06:42,000 –> 00:06:44,479
که در اینجا x برای این فقط صفر خواهد بود.
192
00:06:44,479 –> 00:06:46,840
0 سکه طول می کشد تا مقدار
193
00:06:46,840 –> 00:06:49,680
0 را به دست آوریم. بیایید سعی کنیم از سکه دو استفاده کنیم و اکنون
194
00:06:49,680 –> 00:06:50,720
به سمت راست حرکت می کنیم و با
195
00:06:50,720 –> 00:06:52,720
کوچکترین شروع کردیم و اکنون به سراغ سکه های بعدی می
196
00:06:52,720 –> 00:06:53,680
رویم که می رویم. برای چرخش تمام این
197
00:06:53,680 –> 00:06:55,280
سکهها،
198
00:06:55,280 –> 00:06:56,880
اما در واقع نمیتوانیم از سکه ۲ استفاده
199
00:06:56,880 –> 00:06:57,919
کنیم، زیرا بیشتر از مقداری است
200
00:06:57,919 –> 00:06:59,039
که در حال حاضر استفاده میکنیم،
201
00:06:59,039 –> 00:07:00,800
منطقی نیست که در یک مقدار منفی باقی بماند،
202
00:07:00,800 –> 00:07:03,680
بنابراین دوباره ۵ را امتحان کنید،
203
00:07:03,680 –> 00:07:05,120
نیازی به ادامه نیست.
204
00:07:05,120 –> 00:07:08,560
ما قبلاً مقدار
205
00:07:08,560 –> 00:07:10,639
مورد نیاز پنج را پشت سر گذاشتهایم، بزرگتر از یک است،
206
00:07:10,639 –> 00:07:12,800
بنابراین در اینجا حداقل x
207
00:07:12,800 –> 00:07:15,360
y z فقط x خواهد بود زیرا y z وجود ندارد
208
00:07:15,360 –> 00:07:17,120
و ما میدانیم که صفر است تنها کاری که باید
209
00:07:17,120 –> 00:07:19,440
انجام دهیم این است که یک را به آن اضافه کنیم
210
00:07:19,440 –> 00:07:21,360
تا از صفر برسیم. به یک و اکنون
211
00:07:21,360 –> 00:07:23,280
ما کمترین تعداد سکه مورد نیاز را داریم
212
00:07:23,280 –> 00:07:24,880
مقدار یک را بسازیم و میتوانیم آن را به یادداشت اضافه کنیم
213
00:07:24,880 –> 00:07:26,240
214
00:07:26,240 –> 00:07:28,479
تا این یکی باشد
215
00:07:28,479 –> 00:07:29,759
و
216
00:07:29,759 –> 00:07:32,240
اکنون میتوانیم به تماسگیرنده خود برگردیم که
217
00:07:32,240 –> 00:07:33,440
دو است،
218
00:07:33,440 –> 00:07:35,039
بنابراین همانطور که قبلاً ذکر شد،
219
00:07:35,039 –> 00:07:36,479
همه چیزهایی که
220
00:07:36,479 –> 00:07:39,360
سکه اصلی مورد نیاز است را تا بی نهایت تنظیم میکنیم که
221
00:07:39,360 –> 00:07:40,720
حتی نمیدانیم اگر هنوز میتوانید دو تا بسازید، اما
222
00:07:40,720 –> 00:07:42,560
وقتی یکی برمیگرداند،
223
00:07:42,560 –> 00:07:44,400
میدانیم که حداقل تعداد سکههای
224
00:07:44,400 –> 00:07:45,919
مورد نیاز
225
00:07:45,919 –> 00:07:48,800
پس از استفاده از یک سکه
226
00:07:48,800 –> 00:07:50,319
، یک سکه است
227
00:07:50,319 –> 00:07:51,919
و هر بار که یک شعبه برمیگردد، ما
228
00:07:51,919 –> 00:07:55,120
فقط مید سکههای مورد نیاز را بر این اساس بهروزرسانی میکنیم،
229
00:07:55,120 –> 00:07:55,919
بنابراین
230
00:07:55,919 –> 00:07:57,039
231
00:07:57,039 –> 00:07:59,520
حداقل حداقل سکههای مورد نیاز معادل است.
232
00:07:59,520 –> 00:08:00,720
min از
233
00:08:00,720 –> 00:08:01,520
x
234
00:08:01,520 –> 00:08:04,240
y z
235
00:08:04,240 –> 00:08:07,759
بنابراین اکنون سعی می کنیم با سکه
236
00:08:07,759 –> 00:08:09,280
دو مقدار باقیمانده صفر باشد دو
237
00:08:09,280 –> 00:08:11,280
منهای دو صفر است و می خواهیم در یادداشت بررسی
238
00:08:11,280 –> 00:08:14,080
کنیم که وجود دارد بنابراین
239
00:08:14,080 –> 00:08:17,120
می دانیم که صفر سکه بیشتر طول می کشد
240
00:08:17,120 –> 00:08:19,120
تا مقدار باقی مانده
241
00:08:19,120 –> 00:08:22,800
که حداقل سکه های مورد نیاز را به روز کنیم صفر باشد
242
00:08:22,800 –> 00:08:25,039
و اکنون ما 0.5 را امتحان می کنیم، اما هیچ فایده
243
00:08:25,039 –> 00:08:26,639
ای برای ادامه دادن آن بیشتر از
244
00:08:26,639 –> 00:08:28,479
مقداری است که داریم، بنابراین در اینجا
245
00:08:28,479 –> 00:08:31,039
حداقل مقدار درست است فقط x y وجود ندارد z
246
00:08:31,039 –> 00:08:32,880
، صفر است که ما سکه نبوده
247
00:08:32,880 –> 00:08:34,399
ایم تنها کاری که باید انجام دهیم این است که یک به آن اضافه کنیم. این
248
00:08:34,399 –> 00:08:36,559
طول می کشد یک سکه از صفر به دو برود
249
00:08:36,559 –> 00:08:38,399
و آن مقدار سکه دو است
250
00:08:38,399 –> 00:08:40,399
و میتوانیم این را به یادداشت
251
00:08:40,399 –> 00:08:42,799
یک سکه به من دو اضافه کنیم و اکنون
252
00:08:42,799 –> 00:08:43,919
به عدد سه برمیگردیم،
253
00:08:43,919 –> 00:08:46,160
بنابراین دوباره
254
00:08:46,160 –> 00:08:48,000
سه سکه حداقل باید به بینهایت تنظیم شود
255
00:08:48,000 –> 00:08:50,640
تا زمانی که دو با آن برگردد. مقدار یک
256
00:08:50,640 –> 00:08:52,560
زمانی که این کار انجام شد، سکه های به روز رسانی
257
00:08:52,560 –> 00:08:54,880
باید یک باشد
258
00:08:54,880 –> 00:08:56,880
و ما سعی کردیم نقطه دو
259
00:08:56,880 –> 00:09:00,640
مقدار یک مقدار یادداشت بررسی یک است و علامت
260
00:09:00,640 –> 00:09:02,240
261
00:09:02,240 –> 00:09:04,240
پنج را بررسی کنیم، می دانیم که نمی توانیم ادامه دهیم،
262
00:09:04,240 –> 00:09:05,839
بنابراین آنها به نوعی دو
263
00:09:05,839 –> 00:09:08,480
مورد سهام برای ما خواهند بود. راه حل بازگشتی یک
264
00:09:08,480 –> 00:09:09,920
اگر سکه ای که روی آن هستیم بیشتر از
265
00:09:09,920 –> 00:09:11,440
مقداری است که روی آن هستیم
266
00:09:11,440 –> 00:09:12,399
و
267
00:09:12,399 –> 00:09:14,399
اگر مقداری که به دنبال آن هستیم از قبل
268
00:09:14,399 –> 00:09:16,560
در یادداشت وجود داشته باشد،
269
00:09:16,560 –> 00:09:17,920
فقط تعداد سکه های مورد نیاز برای تشکیل
270
00:09:17,920 –> 00:09:19,440
آن مقدار را برمی گردانیم،
271
00:09:19,440 –> 00:09:21,519
بنابراین من در اینجا هستم سکه های مورد نیاز یک اضافه کردن
272
00:09:21,519 –> 00:09:24,320
یک است و آن را به یادداشت ما اضافه کنید،
273
00:09:24,320 –> 00:09:27,519
بنابراین یک به علاوه یک
274
00:09:27,519 –> 00:09:31,440
دو سکه است تا مقدار سه را به دست
275
00:09:31,440 –> 00:09:34,160
آوریم و وقتی به چهار برگردیم پس از سه
276
00:09:34,160 –> 00:09:35,839
نیز برمی گردیم، می دانیم که مینی سکه های
277
00:09:35,839 –> 00:09:37,440
مورد نیاز در حال حاضر دو سکه بعد از اتمام است.
278
00:09:37,440 –> 00:09:39,120
برای شاخه یک حل شد
279
00:09:39,120 –> 00:09:41,680
حالا بیایید شعبه دو را امتحان کنیم تا از سکه دو استفاده
280
00:09:41,680 –> 00:09:42,800
281
00:09:42,800 –> 00:09:44,160
کنیم و l هستیم eft با
282
00:09:44,160 –> 00:09:45,920
یادداشت بررسی mount two یک سکه طول میکشد تا
283
00:09:45,920 –> 00:09:48,480
دو تا از نقاط
284
00:09:48,480 –> 00:09:50,480
285
00:09:50,480 –> 00:09:52,080
286
00:09:52,080 –> 00:09:54,240
287
00:09:54,240 –> 00:09:55,519
288
00:09:55,519 –> 00:09:58,480
زوج مورد نیاز را بدست آورید. یادداشت را بهروزرسانی کنید،
289
00:09:58,480 –> 00:10:00,320
290
00:10:00,320 –> 00:10:02,640
بنابراین وقتی پنج
291
00:10:02,640 –> 00:10:04,800
دقیقه سکه مورد نیاز را از بینهایت
292
00:10:04,800 –> 00:10:06,399
به دو تغییر دادیم، دو امتیاز طول میکشد تا
293
00:10:06,399 –> 00:10:08,959
پس از استفاده از سکه یک، مقدار باقیمانده
294
00:10:08,959 –> 00:10:12,079
را بدست آوریم، اگر سعی کنیم از سکه دو استفاده
295
00:10:12,160 –> 00:10:13,200
کنیم،
296
00:10:13,200 –> 00:10:15,440
297
00:10:15,440 –> 00:10:17,440
مونت سه باقی میماند که دو امتیاز طول میکشد.
298
00:10:17,440 –> 00:10:20,320
بدون نیاز به آپدیت کردن من در سکه
299
00:10:20,320 –> 00:10:22,000
و بعد از استفاده از نقطه پنج،
300
00:10:22,000 –> 00:10:24,320
مقدار صفر چک در یادداشت باقی مانده است.
301
00:10:24,320 –> 00:10:26,160
302
00:10:26,160 –> 00:10:28,480
303
00:10:28,480 –> 00:10:30,160
304
00:10:30,160 –> 00:10:32,560
حداقل سکه
305
00:10:32,560 –> 00:10:34,720
مورد نیاز است و آن را به یادداشت اضافه کنید، بنابراین
306
00:10:34,720 –> 00:10:37,760
یک سکه طول می کشد تا پنج سکه بسازید
307
00:10:37,760 –> 00:10:41,519
و اکنون به عدد شش برمی گردیم، بنابراین می دانیم که
308
00:10:41,519 –> 00:10:43,519
x معادل
309
00:10:43,519 –> 00:10:46,800
یک است و حداقل سکه ها یک ام خواهد بود،
310
00:10:46,800 –> 00:10:48,640
اکنون
311
00:10:48,640 –> 00:10:51,040
شعبه دو را امتحان می کنیم، بنابراین نقطه دو هستیم. باقی مانده
312
00:10:51,040 –> 00:10:53,519
با مقدار چهار ما این را در یادداشت الف دیده ایم
313
00:10:53,519 –> 00:10:55,200
و این به معنای تکرار نکردن
314
00:10:55,200 –> 00:10:57,279
محاسبات به درستی است که قبلاً انجام دادهایم
315
00:10:57,279 –> 00:10:58,880
و چهار عدد را محاسبه کردهایم، بنابراین تنها کاری که باید
316
00:10:58,880 –> 00:11:01,440
انجام دهیم این است که آن را جستجو کنیم، میدانیم که
317
00:11:01,440 —