C++果物運搬貪欲アルゴリズム実現コード
2012 ワード
C++果物運搬貪欲アルゴリズム実現コード
(1)タイトル説明:
ある果樹園では、明ちゃんはすでにすべての果物を打ち落として、果物の種類によっていくつかの山に分けて、明ちゃんはすべての果物を合成することにしました.合并するたびに、明ちゃんは2つの果物を合并することができて、消耗した体力は2つの果物の重さの和に等しいです.もちろんn�1回合并してから、山になりました.明ちゃんが果物を合併するときに消費した体力は、合併するたびに消費した体力の和に等しい.
各果物の重量が1であると仮定し、果物の種類数と各果物の数が知られていると仮定すると、あなたの任務は合併の順序案を設計し、明ちゃんが消費する体力を最小限に抑え、この最小の体力消費値を出力することです.例えば3種類の果物があり、数は1,2,9の順である.まず1,2スタックを統合し,新しいスタック数は3,体力消費は3である.その後、新しいスタックを元の3番目のスタックと組み合わせて新しいスタックを得て、体力を12に費やします.だから明ちゃんは全部で体力=3+12=15を費やして、15が最小の体力消費値であることを証明することができます.
入力:
各セットのデータ入力は2行を含み、第1行は整数n(1<=n<=10000)であり、果物の種類数を表し、nが0に等しい場合は入力が終了し、処理しない.2行目はn個の整数を含み、スペースで区切られ、i番目の整数(1<=ai<=1000)はi番目の果物の数である.
出力:
各入力セットについて、整数を出力して改行します.この値は、最小の体力消費値です.入力データは、この値が2^31未満であることを保証します.
サンプル入力:
3 9 1 2 0
サンプル出力:
15
(2)この問題は,貪欲アルゴリズム(毎回最小の果物の山を統合する)を用いることができることを考慮し,問題はヘフマン符号化と類似している.コードもHuffman符号化アルゴリズムに基づいて変更され、実現コードは以下の通りである.
PS:コードはその機能を実現するだけで、最適化されていません.Vectorを容器として使用し、消耗した体力値を格納し、実行ごとにExtract_MIN操作は一度Vectorを巡回し,実際には効率が低いため,実際の応用では最小スタック構造を用いて消費した体力値を格納すべきであり,多くの時間を節約できる.
読書に感謝して、みんなを助けることができることを望んで、みんなの当駅に対する支持に感謝します!
(1)タイトル説明:
ある果樹園では、明ちゃんはすでにすべての果物を打ち落として、果物の種類によっていくつかの山に分けて、明ちゃんはすべての果物を合成することにしました.合并するたびに、明ちゃんは2つの果物を合并することができて、消耗した体力は2つの果物の重さの和に等しいです.もちろんn�1回合并してから、山になりました.明ちゃんが果物を合併するときに消費した体力は、合併するたびに消費した体力の和に等しい.
各果物の重量が1であると仮定し、果物の種類数と各果物の数が知られていると仮定すると、あなたの任務は合併の順序案を設計し、明ちゃんが消費する体力を最小限に抑え、この最小の体力消費値を出力することです.例えば3種類の果物があり、数は1,2,9の順である.まず1,2スタックを統合し,新しいスタック数は3,体力消費は3である.その後、新しいスタックを元の3番目のスタックと組み合わせて新しいスタックを得て、体力を12に費やします.だから明ちゃんは全部で体力=3+12=15を費やして、15が最小の体力消費値であることを証明することができます.
入力:
各セットのデータ入力は2行を含み、第1行は整数n(1<=n<=10000)であり、果物の種類数を表し、nが0に等しい場合は入力が終了し、処理しない.2行目はn個の整数を含み、スペースで区切られ、i番目の整数(1<=ai<=1000)はi番目の果物の数である.
出力:
各入力セットについて、整数を出力して改行します.この値は、最小の体力消費値です.入力データは、この値が2^31未満であることを保証します.
サンプル入力:
3 9 1 2 0
サンプル出力:
15
(2)この問題は,貪欲アルゴリズム(毎回最小の果物の山を統合する)を用いることができることを考慮し,問題はヘフマン符号化と類似している.コードもHuffman符号化アルゴリズムに基づいて変更され、実現コードは以下の通りである.
PS:コードはその機能を実現するだけで、最適化されていません.Vectorを容器として使用し、消耗した体力値を格納し、実行ごとにExtract_MIN操作は一度Vectorを巡回し,実際には効率が低いため,実際の応用では最小スタック構造を用いて消費した体力値を格納すべきであり,多くの時間を節約できる.
#include
#include
using namespace std;
/*
*
*/
int Extract_MIN(vector& v)
{
if(v.size() == 0)
return -1;
int i=0, min_pos = 0;
vector::iterator iter = v.begin();
vector::iterator min_iter = v.begin();
for(; iter!=v.end(); ++iter)
if((*iter) v;
int i=0;
for(i=0; i>n)
{
if(n == 0)
break;
int* data = new int[n];
int i=0;
for(; i>data[i];
cout<
読書に感謝して、みんなを助けることができることを望んで、みんなの当駅に対する支持に感謝します!