 سؤال
مي‌دانيم كه در بين n سكه، يكي تقلبي است و بقيه سالم هستند. وزن هر سكه‌ي تقلبي از سكه‌ي سالم كم‌تر است و وزن تمام سكه‌هاي سالم يكسان است. مي‌خواهيم با استفاده از يك ترازوي دو كفه‌ي سكه تقلبي را پيدا كنيم.
حالا سؤال ما از شما اينه كه الگوريتمي (يا برنامه‌اي) بنويسيد كه با دريافت n، حداقل مقدار k را پيدا كند به‌طوري كه با حداكثر k بار استفاده از ترازو بتوان سكه‌ي تقلبي را تشخيص داد و در هر مرحله، سكه‌هايي كه بايد با هم مقايسه شوند را روي صفحه‌ي نمايش چاپ كند و نتيجه مقايسه‌ي اين سكه‌ها را از وردي دريافت كند. مثلاً: كاربر كامپيوتر Enter n ? 10 Minimum number of comparisons : 3 1:compare {1,2,3} and {4,5,6}.(<=>) = 2:compare {7,8} and {9,10}.(< = >) ? > 3:compare {9} and {10}.(< = >) ? < Coin #9 is counterfeit . |