貪心算法實(shí)驗(yàn)

1、實(shí)驗(yàn)三貪心算法的應(yīng)用一、實(shí)驗(yàn)?zāi)康恼莆肇澬乃惴ǖ幕靖拍詈蛢蓚€(gè)基本要素熟練掌握貪心算法解決問題的基本步驟。學(xué)會利用貪心算法解決實(shí)際問題。二、實(shí)驗(yàn)內(nèi)容1.問題描述：題目一：硬幣找錢問題設(shè)有6種不同面值的硬幣，各硬幣的面值分別為5分、1角、2角、5角、1 元和2元?，F(xiàn)在要用這些面值的硬幣來購物和找錢。購物時(shí)可以使用的各種面值 的硬幣個(gè)數(shù)存于數(shù)組Coins1:6中，假設(shè)商店里各面值的硬幣有足夠多。對于 給定的付款金額，計(jì)算使用硬幣個(gè)數(shù)最少的交易方案。輸入數(shù)據(jù)的每一行有6 個(gè)整數(shù)和一個(gè)有2位小數(shù)的實(shí)數(shù)，分別表示可以使用的各種面值的硬幣個(gè)數(shù)和付 款金額。輸出為交易所需要的最少硬幣個(gè)數(shù)，如果不可能完成交易，

2、則輸出 impossible。輸入數(shù)據(jù)示例2 4 2 2 1 00.952 4 2 0 1 00.55輸出示例23題目二：會場安排問題假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設(shè)計(jì) 一個(gè)有效的貪心算法來進(jìn)行安排。試編程實(shí)現(xiàn)對于給定的k個(gè)待安排活動，計(jì)算 使用的最少會場。輸入數(shù)據(jù)中，第一行是k的值，接下來的k行中，每行有2 個(gè)正整數(shù)，分別表示k個(gè)待安排活動的開始時(shí)間和結(jié)束時(shí)間，時(shí)間以0點(diǎn)開始的 分鐘計(jì)。輸出為最少的會場數(shù)。輸入數(shù)據(jù)示例52312 2825 3527 8036 50輸出數(shù)據(jù)3題目三：程序存儲問題設(shè)有n個(gè)程序1,2,3,n要存放在長度為L的磁帶上。程序i存放在磁帶

3、 上的長度是li,1ino要求確定這n個(gè)程序在磁帶上的一個(gè)存儲方案，使得能 夠在磁帶上存儲盡可能多的程序。輸入數(shù)據(jù)中，第一行是2個(gè)正整數(shù)，分別表示 程序文件個(gè)數(shù)和磁帶長度L。接下來的1行中，有n個(gè)正整數(shù)，表示程序存放在 磁帶上的長度。輸出為最多可以存儲的程序個(gè)數(shù)。輸入數(shù)據(jù)示例6 503 13 8 80 20輸出數(shù)據(jù)5題目四：汽車加油問題一輛汽車加滿油后,可行使n千米。旅途中有若十個(gè)加油站。若要使沿途加 油次數(shù)最少，設(shè)計(jì)一個(gè)有效算法，對于給定的n和k個(gè)加油站位置，指出應(yīng)在哪 些加油站停靠加油才能使加油次數(shù)最少。輸入數(shù)據(jù)中，第一行有2個(gè)正整數(shù)，分 別表示汽車加滿油后可行駛n千米，且旅途中有k個(gè)加油

4、站。接下來的1行中， 有k+1個(gè)整數(shù)，表示第k個(gè)加油站與第k-1個(gè)加油站之間的距離。第0個(gè)加油站 表示出發(fā)地，汽車已加滿油。第k+1個(gè)加油站表示目的地。輸出為最少的加油次 數(shù)，如果無法到達(dá)目的地，則輸出“No Solution”。實(shí)驗(yàn)提示：把兩加油站的距離放在數(shù)組中，a1.k 表示從起始位置開始跑，經(jīng)過k個(gè) 加油站，ai表示第i-1個(gè)加油站到第i個(gè)加油站的距離。汽車在運(yùn)行的過程 中如果能跑到下一個(gè)站則不加油，否則要加油。輸入數(shù)據(jù)示例7 71 2 3 4 5 1 6 6輸出數(shù)據(jù)4數(shù)據(jù)輸入：個(gè)人設(shè)定，由鍵盤輸入。要求：1）上述題目任選一做。上機(jī)前，完成程序代碼的編寫2）獨(dú)立完成實(shí)驗(yàn)及實(shí)驗(yàn)報(bào)告三、實(shí)驗(yàn)步驟理解算法思想和問題要求；編程實(shí)現(xiàn)題目要求；上機(jī)輸入和調(diào)試自己所編的程序；驗(yàn)證分析實(shí)驗(yàn)結(jié)果；整理出實(shí)驗(yàn)報(bào)告。附：實(shí)驗(yàn)報(bào)告的主要內(nèi)容實(shí)驗(yàn)?zāi)康膯栴}描述算法設(shè)計(jì)包含：數(shù)據(jù)