چگونه می توان تمام ترکیب سکه ها را در صورت مقداری ارزش دلار پیدا کرد [بسته]

آیا می خواهید این سوال را بهبود ببخشید؟این سؤال را به روز کنید تا فقط با ویرایش این پست روی یک مشکل متمرکز شود.

1 سال پیش بسته شد.

من یک قطعه کد را پیدا کردم که چند ماه پیش برای مصاحبه مقدماتی می نوشتم.

مطابق اظهار نظر من ، سعی در حل این مشکل داشت:

با توجه به ارزش دلار در سنت (به عنوان مثال 200 = 2 دلار ، 1000 = 10 دلار) ، تمام ترکیب سکه هایی را که ارزش دلار را تشکیل می دهند ، پیدا کنید. فقط سکه های (1 ¢) ، نیکل (5 ¢) ، Dimes (10 ¢) و چهارم (25 ¢) مجاز است.

به عنوان مثال ، اگر 100 داده شد ، پاسخ باید باشد:

من معتقدم که این امر می تواند به هر دو روش تکراری و بازگشتی حل شود. راه حل بازگشتی من کاملاً حشره دار است و من نمی دانم که افراد دیگر چگونه این مشکل را حل می کنند. بخش دشوار این مشکل باعث می شود تا حد ممکن کارآمد باشد.

John T: کد گلف؟من هرگز از این اصطلاح نشنیده ام! به هر حال ، من امیدوارم که پاسخ های جالبی را ببینم ، زیرا جامعه می تواند هر مشکلی را حل کند

من همچنین سعی خواهم کرد که وقتی به خانه رسیدم جواب خود را ارسال کنم. هنوز در محل کار است و من نباید بیش از حد وقت خود را صرف کنم.

Golf Code Code به حل یک مشکل در کمترین شخصیت ممکن ، با زبان برنامه نویسی مورد نظر شما اشاره دارد. در اینجا مواردی وجود دارد که در این وب سایت انجام شده است: stackoverflow.com/search؟q=code+golf

37 پاسخ 37

مدتها پیش یک بار به این موضوع نگاه کردم ، و شما می توانید نوشتن نامه کوچک من را در مورد آن بخوانید. در اینجا منبع Mathematica است.

با استفاده از توابع تولید کننده ، می توانید یک راه حل ثابت زمان ثابت برای مشکل دریافت کنید. ریاضیات بتونی گراهام ، نات و پاتاشنیک کتابی برای این کار است و حاوی بحث نسبتاً گسترده ای در مورد این مشکل است. اساساً شما یک چند جمله ای را تعریف می کنید که ضریب N تعداد روش های تغییر برای N دلار است.

صفحات 4-5 از نوشتن نشان می دهد که چگونه می توانید از Mathematica (یا هر سیستم جبر رایانه ای مناسب دیگر) برای محاسبه پاسخ برای 10^10^6 دلار در دو ثانیه در سه خط کد استفاده کنید.

(و این به اندازه کافی پیش بود که چند ثانیه در یک پنتیوم 75 مگاهرتز است.)

پاسخ خوب ، اما مبهم های جزئی: توجه داشته باشید که (1) این تعداد روش ها را نشان می دهد ، در حالی که به دلایلی این سوال مجموعه واقعی از همه راه ها را می پرسد. البته ، هیچ راهی برای یافتن مجموعه در زمان چند جمله ای وجود ندارد ، زیرا خود خروجی دارای ورودی های فوق العاده زیادی است (2) قابل بحث است که آیا یک عملکرد تولید کننده یک "فرم بسته" است (به کتاب فوق العاده هربرت ویلف تولید می شود: MATH. upe. edu/~wilf/downldgf.html) و اگر منظور شما از عبارتی مانند (1+√5)^n است ، برای محاسبه زمان ω (log n) طول می کشد ، نه زمان ثابت.

مقدمه ملایم برای برنامه نویسی پویا. همچنین ، من هر کسی را که مشکل دنباله ای دارد ، تشویق می کند تا تولید تولید را بخواند.

خیلی ممنون اندرو. این توضیح خیلی به من کمک کرد. ارسال عملکرد Scala در زیر .. آیا برخی از آنها به آن احتیاج دارد

من معتقدم که این سؤال در ابتدا نیاز به تصحیح جزئی دارد زیرا می پرسد "با استفاده از سکه های 1- ، 10- ، 25- ، 50- و 100 درصد؟"اما پس از آن نوشتن مجموعه A را به عنوان دامنه f تعریف می کند اما a =<1,5,10,25,50,100>بشردر لیست سکه های Cent باید 5- وجود داشته باشد. در غیر این صورت نوشتن فوق العاده بود ، متشکرم!

توجه: این فقط تعداد راهها را نشان می دهد.

این تعداد از تعداد راه حل های چند جمله ای N1 * سکه (0) + N2 * سکه (1) + ناشی می شود.+ * سکه (n-1) = پول. بنابراین برای پول = 0 و سکه = لیست (1،2،5،10) تعداد ترکیبات (N1 ، N2 ، N3 ، N4) 1 و راه حل (0 ، 0 ، 0 ، 0) است.

من نمی توانم سرم را به این دلیل بپوشم که چرا این اجرا کار می کند. آیا کسی می تواند الگوریتم را پشت سر بگذارد؟

من معتقدم که ، اگر پول == 0 اما سکه. بنابراین ، ممکن است در صورت سکه ها بهتر خدمت کند. پول<0 condition is ck'd for first.

من از یک راه حل بازگشتی طرفداری می کنم. شما لیستی از فرقه ها دارید ، اگر کوچکترین مورد می تواند به طور مساوی هر مبلغ ارز باقیمانده را تقسیم کند ، این باید خوب باشد.

در اصل ، شما از بزرگترین به کوچکترین فرقه ها حرکت می کنید. بازگشتی ،

1. شما یک کل فعلی برای پر کردن و بزرگترین فرقه (با بیش از 1 باقی مانده) دارید. اگر فقط 1 فرقه باقی مانده باشد ، فقط یک راه برای پر کردن کل وجود دارد. شما می توانید از نسخه های 0 تا K از فرقه فعلی خود استفاده کنید به گونه ای که فرقه k * cur
2. برای 0 تا k ، عملکرد را با کل اصلاح شده و بزرگترین فرقه تماس بگیرید.
3. نتایج را از 0 به k اضافه کنید. این چند راه است که می توانید کل خود را از فرقه فعلی در پایین پر کنید. این شماره را برگردانید.

در اینجا نسخه Python من از مشکل بیان شده شما ، برای 200 سنت است. من 1463 راه دریافت می کنم. این نسخه تمام ترکیبات و تعداد نهایی را چاپ می کند.

شما می توانید دو خط آخر عملکرد را با "جمع بازگشت (count_combs (.)) جایگزین کنید." - به این ترتیب لیست به هیچ وجه تحقق نمی یابد.:)

همانطور که در سؤال دیگر بحث شد ، اگر لیست فرقه ها 1 به عنوان آخرین مقدار نداشته باشد ، این کد خروجی نادرست را ارائه می دهد. در صورت بلوک برای رفع آن می توانید مقدار کمی کد را به درونی اضافه کنید (همانطور که در پاسخ خود به سوال دیگر توصیف می کنم).

در اینجا برخی از کد های C ++ کاملاً ساده برای حل مشکلی که درخواست کرده است همه ترکیبات نشان داده شود ، آورده شده است.

اما من در مورد مشکل فرعی فقط محاسبه تعداد ترکیبات کاملاً شیفته هستم. من گمان می کنم یک معادله بسته برای آن وجود دارد.

من فکر می کنم خیلی ساده است. در اصل ، ایده این است که همه محله ها را تکرار کنید (با استفاده از 0،1،2 .. حداکثر) ، و سپس بر اساس چهارم مورد استفاده و غیره از طریق همه سکه ها تکرار کنید.

نکته منفی برای این راه حل این است: اگر سکه های 50 درصد ، 100 درصد ، 500 درصد وجود داشته باشد ، باید از حلقه های 6 سطح استفاده کنیم.

این بسیار بد است ، اگر فرقه پویا دارید یا می خواهید یک فرقه دیگر اضافه کنید ، این کار نخواهد کرد.

مشکل فرعی یک مشکل برنامه نویسی پویا معمولی است.

راه حل های پویا شما نیاز به K طول C منهای 1 دارد. کمی گیج کننده است. شما می توانید آن را به راحتی تغییر دهید تا از طول واقعی C پشتیبانی کنید

کد از جاوا برای حل این مشکل استفاده می کند و همچنین کار می کند. این روش ممکن است به دلیل حلقه های خیلی زیاد ایده خوبی نباشد ، اما واقعاً یک راه مستقیم به جلو است.

این یک سوال واقعاً قدیمی است ، اما من در جاوا یک راه حل بازگشتی به وجود آوردم که از سایرین کوچکتر به نظر می رسید ، بنابراین در اینجا می رود -

بگذارید C (I ، J) مجموعه ای از ترکیبات ساخت من با استفاده از مقادیر موجود در مجموعه J.

شما می توانید C را به این ترتیب تعریف کنید:

(اول (j) به طرز قطعی عنصری از مجموعه را می گیرد)

این یک عملکرد بسیار بازگشتی است. و اگر از Memoization استفاده می کنید ، از نظر منطقی کارآمد است ؛)

حق با شماست: J را به عنوان یک لیست انتخاب کنید و نه به عنوان مجموعه: سپس اول (j) عنصر اول را برای شما به ارمغان می آورد و J First (J) بقیه لیست را به شما می دهد.

نیمه هک برای حل مسئله ترکیبی منحصر به فرد - سفارش نزولی نیرو:

این کار کند خواهد شد زیرا از آن یادآوری نمی شود ، اما شما این ایده را می گیرید.

این پاسخ من در پایتون است. از بازگشت استفاده نمی کند:

هر دو: از طریق تمام فرقه ها از بالا تا پایین ، یکی از فرقه ها را بگیرید ، از کل requried تفریق کنید ، سپس دوباره به باقی بماند (محدود کردن فرقه های قابل حمل برای برابر یا پایین تر از مقدار تکرار فعلی.)

اگر سیستم ارز اجازه می دهد ، یک الگوریتم حریص ساده که تا حد امکان از هر سکه استفاده می کند ، با بالاترین ارزش ارز شروع می شود.

در غیر این صورت ، برنامه نویسی پویا برای یافتن یک راه حل بهینه به سرعت لازم است زیرا این مشکل در اصل مشکل Knapsack است.

به عنوان مثال ، اگر یک سیستم ارزی سکه ها را داشته باشد: ، راه حل حریص برای 24 AS تغییر می کند ، اما راه حل بهینه واقعی این است

ویرایش: من فکر کردم که ما در حال تغییر بهینه هستیم ، و تمام راه های ایجاد یک دلار را ذکر نمی کنیم. مصاحبه اخیر من پرسید که چگونه تغییر ایجاد کند ، بنابراین من قبل از اتمام برای خواندن این سؤال به جلو پریدم.

مشکل لزوماً برای یک دلار نیست - می تواند 2 یا 23 باشد ، بنابراین راه حل شما هنوز تنها صحیح است.

من می دانم که این یک سوال بسیار قدیمی است. من در حال جستجوی پاسخ مناسب بودم و نتوانستم چیزی را پیدا کنم که ساده و رضایت بخش باشد. مدتی مرا گرفت اما توانست چیزی را کم کند.

این یک راه حل JavaScript است و از بازگشت استفاده می کند.

در زبان برنامه نویسی Scala من آن را اینگونه انجام می دهم:

این یک الگوریتم بازگشتی ساده است که یک لایحه را می گیرد ، سپس یک صورتحساب کوچکتر را به صورت بازگشتی می گیرد تا اینکه به این جمع برسد ، سپس یک لایحه دیگر از همان فرقه را می گیرد و دوباره بازگردد. برای تصویر به خروجی نمونه زیر مراجعه کنید.

موارد زیر را چاپ می کند:

Duh ، من الان احساس احمقانه می کنم. در زیر یک راه حل بیش از حد پیچیده وجود دارد که من آن را حفظ می کنم زیرا این یک راه حل است. یک راه حل ساده این است:

در اینجا راه حل دیگر است. این راه حل بر اساس این مشاهدات است که هر سکه از سایر موارد دیگر است ، بنابراین می توان آنها را از نظر آنها نشان داد.

بنابراین ، برای 37 سکه ، به عنوان مثال:

این ورودی وبلاگ این مشکل را حل می کند مانند مشکل برای چهره های یک طنز XKCD. یک تغییر ساده در موارد دیکته و مقدار دقیق کادوی همه راه حل ها را برای مشکل شما نیز به همراه خواهد داشت.

اگر مشکل پیدا کردن تغییری بود که از کمترین هزینه استفاده می کرد ، یک الگوریتم حریص ساده و بی تکلف که از بیشترین سکه با ارزش استفاده می کرد ، ممکن است برای برخی از ترکیبات سکه ها و مقدار هدف به خوبی شکست بخورد. به عنوان مثال اگر سکه هایی با مقادیر 1 ، 3 و 4 وجود دارد. و مقدار هدف 6 است و الگوریتم حریص ممکن است سه سکه از ارزش 4 ، 1 و 1 را پیشنهاد کند که به راحتی می توان دریافت که می توانید از هر یک از مقدار 3 استفاده کنید.

من این قطعه کد شسته و رفته را در کتاب "پایتون برای تجزیه و تحلیل داده ها" توسط O'Reily پیدا کردم. از اجرای تنبل و مقایسه Int استفاده می کند و تصور می کنم با استفاده از اعشار می تواند برای سایر فرقه ها اصلاح شود. بگذار ببینم این برای تو چگونه کار میکند!

این بهبود پاسخ Zihan است. تعداد زیادی از حلقه های غیر ضروری زمانی اتفاق می افتد که فرقه فقط 1 درصد باشد.

این بصری و غیر قابل تکرار است.

شما نمی توانید این راه حل را تعمیم دهید ، بنابراین به عنوان مثال یک عنصر جدید در این حالت باید دیگری را برای حلقه اضافه کنید

راه حل ساده جاوا:

بسیاری از تغییرات در اینجا اما نتوانسته است یک راه حل PHP برای تعداد ترکیبات در هر جایی پیدا کند ، بنابراین من یکی را اضافه می کنم.

در اینجا یک عملکرد C# وجود دارد:

از آن مانند این استفاده کنید:

در زیر یک برنامه پایتون برای یافتن همه ترکیبات پول ارائه شده است. این یک راه حل برنامه نویسی پویا با زمان سفارش (n) است. پول 1،5،10،25 است

ما از ردیف پول 1 تا Row Money 25 (4 ردیف) عبور می کنیم. Row Money 1 حاوی شمارش است اگر ما فقط پول 1 را در محاسبه تعداد ترکیبات در نظر بگیریم. Row Money 5 با گرفتن Count در Row Money R برای همان پول نهایی به علاوه 5 تعداد قبلی در ردیف خود (موقعیت فعلی منهای 5) ، هر ستون را تولید می کند. Row Money 10 از Row Money 5 استفاده می کند ، که شامل تعداد 1،5 است و در 10 تعداد قبلی (موقعیت فعلی منهای 10) اضافه می کند. Row Money 25 از Row Money 10 استفاده می کند ، که حاوی شمارش برای پول ردیف 1،5،10 به علاوه 25 تعداد قبلی است.

به عنوان مثال ، اعداد [1] [12] = اعداد [0] [12] + اعداد [1] [7] (7 = 12-5) که منجر به 3 = 1 + 2 می شود. اعداد [3] [12] = اعداد [2] [12] + اعداد [3] [9] (-13 = 12-25) که منجر به 4 = 0 + 4 می شود ، زیر ا-13 کمتر از 0 است.