مقدمه
در دهکده‌ی اسرارآمیز Coinholt، شما پشت پیشخوان نانوایی‌تان ایستاده‌اید و دسته‌ای تازه از شیرینی‌ها را می‌چینید.
در به صدا در می‌آید و باز می‌شود و Denara وارد می‌شود؛ بازرگانی ماهر که چشمی تیزبین برای کالاهای باکیفیت دارد.
پس از صرف غذایی سریع، سکه‌ای درخشان را روی پیشخوان می‌لغزاند که ارزشی برابر با ۱۰۰ واحد دارد.
لبخند می‌زنید، سکه را برمی‌دارید و نگاهی به هزینه‌ی کل غذا می‌اندازید: ۸۸ واحد.
یعنی باید ۱۲ واحد باقی پول پس بدهید.
Denara با انتظار دستش را دراز می‌کند.
«فقط کمترین تعداد سکه را به من بدهید»، با لبخندی می‌گوید.
«کیسه‌ی من از قبل پُر است و نمی‌خواهم در راه خطر گم شدنشان را بپذیرم.»
می‌دانید که چند گزینه دارید.
«برای باقی پول، Lumis (به ارزش ۱۰ واحد)، Viras (به ارزش ۵ واحد) و Zenth (به ارزش ۲ واحد) در دسترس داریم.»
شما به‌سرعت احتمال‌ها را در ذهن خود حساب می‌کنید:
- یک Lumis (۱ × ۱۰ واحد) + یک Zenth (۱ × ۲ واحد) = در مجموع ۲ سکه
- دو Viras (۲ × ۵ واحد) + یک Zenth (۱ × ۲ واحد) = در مجموع ۳ سکه
- شش Zenth (۶ × ۲ واحد) = در مجموع ۶ سکه
«بهترین انتخاب دو سکه است: یک Lumis و یک Zenth»، می‌گویید و باقی پول را به او می‌دهید.
Denara لبخند می‌زند و آشکارا تحت تأثیر قرار گرفته است.
«مثل همیشه، درست انجامش دادید.»
دستورالعمل‌ها
کمترین تعداد سکه را تعیین کنید که به مشتری داده شود، به‌طوری که مجموع ارزش آن‌ها با مقدار درست خرد برابر باشد.
مثال‌ها
- مقدار ۱۵ با ارزش‌های سکه‌ی موجودِ [1, 5, 10, 25, 100] باید یک سکه به ارزش 5 و یک سکه به ارزش 10، یا [5, 10] را برگرداند.
- مقدار ۴۰ با ارزش‌های سکه‌ی موجودِ [1, 5, 10, 25, 100] باید یک سکه به ارزش 5، یک سکه به ارزش 10 و یک سکه به ارزش 25، یا [5, 10, 25] را برگرداند.
واژه‌ها
find-fewest-coins ( coins target -- result ) یک آرایه از ارزش‌های سکه برمی‌گرداند که مجموعشان target است. coins یک مجموعه‌ی هش است (مثلاً HS{ 1 5 10 25 })؛ برای کار با آن از واژه‌های واژگان sets (مانند members، in? و …) استفاده کنید.
وقتی هیچ ترکیبی از coins نتواند target را بسازد، خطای cannot-make-change را پرتاب کنید.
