c語言貪心演算法
//4d5 貪心演算法 單源最短路徑問題
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int N = 5;
const int M = 1000;
ifstream fin("4d5.txt");
template<class Type>
void Dijkstra(int n,int v,Type dist[],int prev[],Type c[][N+1]);
void Traceback(int v,int i,int prev[]);//輸出最短路徑 v源點，i終點
int main()
{
int v = 1;//源點為1
int dist[N+1],prev[N+1],c[N+1][N+1];
cout<<"有向圖權的矩陣為："<<endl;
for(int i=1; i<=N; i++)
{
for(int j=1; j<=N; j++)
{
fin>>c[i][j];
cout<<c[i][j]<<" ";
}
cout<<endl;
}
Dijkstra(N,v,dist,prev,c);
for(int i=2; i<=N; i++)
{
cout<<"源點1到點"<<i<<"的最短路徑長度為:"<<dist[i]<<"，其路徑為";
Traceback(1,i,prev);
cout<<endl;
}
return 0;
}
template<class Type>
void Dijkstra(int n,int v,Type dist[],int prev[],Type c[][N+1])
{
bool s[N+1];
for(int i=1; i<=n; i++)
{
dist[i] = c[v][i];//dist[i]表示當前從源到頂點i的最短特殊路徑長度
s[i] = false;
if(dist[i] == M)
{
prev[i] = 0;//記錄從源到頂點i的最短路徑i的前一個頂點
}
else
{
prev[i] = v;
}
}
dist[v] = 0;
s[v] = true;
for(int i=1; i<n; i++)
{
int temp = M;
int u = v;//上一頂點
//取出V-S中具有最短特殊路徑長度的頂點u
for(int j=1; j<=n; j++)
{
if((!s[j]) && (dist[j]<temp))
{
u = j;
temp = dist[j];
}
}
s[u] = true;
//根據作出的貪心選擇更新Dist值
for(int j=1; j<=n; j++)
{
if((!s[j]) && (c[u][j]<M))
{
Type newdist = dist[u] + c[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
//輸出最短路徑 v源點，i終點
void Traceback(int v,int i,int prev[])
{
if(v == i)
{
cout<<i;
return;
}
Traceback(v,prev[i],prev);
cout<<"->"<<i;
}
Ⅱ C語言，貪心演算法，貨幣找零問題
貪心演算法找零就是現實中從最大面額開始找的思路。不代表是最優解，只是演算法之一。
由於面額輸入順序不定，我先對輸入的面額進行降序排序。
下面代碼：
#include <stdio.h>
#include <malloc.h>
int main()
{
int i,j,m,n,*ns=NULL,*cn=NULL,sum=0;
printf("請輸入總金額m及零錢種類n："),scanf("%d",&m),scanf("%d",&n);
printf("請分別輸入%d種零錢的面額： ",n);
if(!(ns=(int *)malloc(sizeof(int)*n))) return 1;
if(!(cn=(int *)malloc(sizeof(int)*n))) return 1;
for(i=0;i<n;i++) scanf("%d",&ns[i]);
//------------考慮輸入面額順序不定，先對面額進行降序排列（如按照降序輸入，該段可刪除）
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(ns[j]>ns[i]) ns[j]^=ns[i],ns[i]^=ns[j],ns[j]^=ns[i];
//-------------------------------------------------------------------
for(i=0;i<n;i++)//貪心演算法，從最大面額開始
if(m>=ns[i])
cn[i]=m/ns[i],m=m%ns[i],sum+=cn[i],printf("%d元%d張 ",ns[i],cn[i]);
printf(" 最少使用零錢%d張 ",sum);
return 0;
}
Ⅲ 程序員演算法基礎——貪心演算法
貪心是人類自帶的能力，貪心演算法是在貪心決策上進行統籌規劃的統稱。
比如一道常見的演算法筆試題---- 跳一跳 ：
我們自然而然能產生一種解法：盡可能的往右跳，看最後是否能到達。
本文即是對這種貪心決策的介紹。
狹義的貪心演算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選纖啟擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解；這種貪心演算法是動態規劃的一種特例。 能用貪心解決的問題，也可以用動態規劃解決。
而廣義的貪心指的是一種通用的貪心策略，基於當前局面而進行貪心決策。以 跳一跳 的題目為例：
我們發現的題目的核心在於 向右能到達的最遠距離 ，我們用maxRight來表示；
此時有一種貪心的策略：從第1個盒子開始向右遍歷，對於每個經過的盒子，不斷更新maxRight的值。
貪毀局如心的思考過程類似動態規劃，依舊是兩步： 大事化小 ， 小事化了 。
大事化小：
一個較大的臘山問題，通過找到與子問題的重疊，把復雜的問題劃分為多個小問題；
小事化了：
從小問題找到決策的核心，確定一種得到最優解的策略，比如跳一跳中的 向右能到達的最遠距離 ；
在證明局部的最優解是否可以推出全局最優解的時候，常會用到數學的證明方式。
如果是動態規劃：
要湊出m元，必須先湊出m-1、m-2、m-5、m-10元，我們用dp[i]表示湊出i元的最少紙幣數；
有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;
容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；
根據以上遞推方程和初始化信息，可以容易推出dp[1~m]的所有值。
似乎有些不對？ 平時我們找零錢有這么復雜嗎？
從貪心演算法角度出發，當m>10且我們有10元紙幣，我們優先使用10元紙幣，然後再是5元、2元、1元紙幣。
從日常生活的經驗知道，這么做是正確的，但是為什麼？
假如我們把題目變成這樣，原來的策略還能生效嗎？
接下來我們來分析這種策略：
已知對於m元紙幣，1，2，5元紙幣使用了a，b，c張，我們有a+2b+5c=m；
假設存在一種情況，1、2、5元紙幣使用數是x，y，z張，使用了更少的5元紙幣（z<c），且紙幣張數更少（x+y+z<a+b+c），即是用更少5元紙幣得到最優解。
我們令k=5*(c-z)，k元紙幣需要floor(k/2)張2元紙幣，k%2張1元紙幣；（因為如果有2張1元紙幣，可以使用1張2元紙幣來替代，故而1元紙幣只能是0張或者1張）
容易知道，減少(c-z)張5元紙幣，需要增加floor(5*(c-z)/2)張2元紙幣和(5*(c-z))%2張紙幣，而這使得x+y+z必然大於a+b+c。
由此我們知道不可能存在使用更少5元紙幣的更優解。
所以優先使用大額紙幣是一種正確的貪心選擇。
對於1、5、7元紙幣，比如說要湊出10元，如果優先使用7元紙幣，則張數是4；（1+1+1+7）
但如果只使用5元紙幣，則張數是2；（5+5）
在這種情況下，優先使用大額紙幣是不正確的貪心選擇。（但用動態規劃仍能得到最優解）
如果是動態規劃：
前i秒的完成的任務數，可以由前面1~i-1秒的任務完成數推過來。
我們用 dp[i]表示前i秒能完成的任務數 ；
在計算前i秒能完成的任務數時，對於第j個任務，我們有兩種決策：
1、不執行這個任務，那麼dp[i]沒有變化；
2、執行這個任務，那麼必須騰出來(Sj, Tj)這段時間，那麼 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；
比如說對於任務j如果是第5秒開始第10秒結束，如果i>=10，那麼有 dp[i]=max(dp[i], dp[5] + 1)； （相當於把第5秒到第i秒的時間分配給任務j）
再考慮貪心的策略，現實生活中人們是如何安排這種多任務的事情？我換一種描述方式：
我們自然而然會想到一個策略： 先把結束時間早的兼職給做了！
為什麼？
因為先做完這個結束時間早的，能留出更多的時間做其他兼職。
我們天生具備了這種優化決策的能力。
這是一道 LeetCode題目 。
這個題目不能直接用動態規劃去解，比如用dp[i]表示前i個人需要的最少糖果數。
因為（前i個人的最少糖果數）這種狀態表示會收到第i+1個人的影響，如果a[i]>a[i+1]，那麼第i個人應該比第i+1個人多。
即是 這種狀態表示不具備無後效性。
如果是我們分配糖果，我們應該怎麼分配？
答案是： 從分數最低的開始。
按照分數排序，從最低開始分，每次判斷是否比左右的分數高。
假設每個人分c[i]個糖果，那麼對於第i個人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默認為0，如果在計算i的時候,c[i-1]為0，表示i-1的分數比i高）
但是，這樣解決的時間復雜度為 O(NLogN) ，主要瓶頸是在排序。
如果提交，會得到 Time Limit Exceeded 的提示。
我們需要對貪心的策略進行優化：
我們把左右兩種情況分開看。
如果只考慮比左邊的人分數高時，容易得到策略：
從左到右遍歷，如果a[i]>a[i-1]，則有c[i]=c[i-1]+1；否則c[i]=1。
再考慮比右邊的人分數高時，此時我們要從數組的最右邊，向左開始遍歷：
如果a[i]>a[i+1], 則有c[i]=c[i+1]+1；否則c[i]不變；
這樣講過兩次遍歷，我們可以得到一個分配方案，並且時間復雜度是 O(N) 。
題目給出關鍵信息：1、兩個人過河，耗時為較長的時間；
還有隱藏的信息：2、兩個人過河後，需要有一個人把船開回去；
要保證總時間盡可能小，這里有兩個關鍵原則： 應該使得兩個人時間差盡可能小（減少浪費），同時船回去的時間也盡可能小（減少等待）。
先不考慮空船回來的情況，如果有無限多的船，那麼應該怎麼分配？
答案： 每次從剩下的人選擇耗時最長的人，再選擇與他耗時最接近的人。
再考慮只有一條船的情況，假設有A/B/C三個人，並且耗時A<B<C。
那麼最快的方案是：A+B去, A回；A+C去；總耗時是A+B+C。（因為A是最快的，讓其他人來回時間只會更長， 減少等待的原則 ）
如果有A/B/C/D四個人，且耗時A<B<C<D，這時有兩種方案：
1、最快的來回送人方式，A+B去；A回；A+C去，A回；A+D去； 總耗時是B+C+D+2A （減少等待原則）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；總耗時是 3B+D+A （減少浪費原則）
對比方案1、2的選擇，我們發現差別僅在A+C和2B；
為何方案1、2差別里沒有D？
因為D最終一定要過河，且耗時一定為D。
如果有A/B/C/D/E 5個人，且耗時A<B<C<D<E，這時如何抉擇？
仍是從最慢的E看。（參考我們無限多船的情況）
方案1，減少等待；先送E過去，然後接著考慮四個人的情況；
方案2，減少浪費；先送E/D過去，然後接著考慮A/B/C三個人的情況；（4人的時候的方案2）
到5個人的時候，我們已經明顯發了一個特點：問題是重復，且可以由子問題去解決。
根據5個人的情況，我們可以推出狀態轉移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根據我們考慮的1、2、3、4個人的情況，我們分別可以算出dp[i]的初始化值：
dp[1] = a[1];
dp[2] = a[2];
dp[3] = a[2]+a[1]+a[3];
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);
由上述的狀態轉移方程和初始化值，我們可以推出dp[n]的值。
貪心的學習過程，就是對自己的思考進行優化。
是把握已有信息，進行最優化決策。
這里還有一些收集的 貪心練習題 ，可以實踐練習。
這里 還有在線分享，歡迎報名。
Ⅳ c語言問題急！！！（用貪心演算法）
這個問題不是很難,我寫了就怕你看不懂,不懂問我啊,4個循環就可以了.
qq 64924930
調試通過!
main()
{
int i,a[5],b[4],c[4];
/* define the type of the money*/
a[1]=25;
a[2]=10;
a[3]=5;
a[4]=1;
printf("please input you money (fen):\n");
scanf("%d",&b[0]);
for (i=1;i<=4;i++)
{
b[i]=b[i-1]%a[i]; /*take n 25 off and money left*/
c[i]=(b[i-1]-b[i])/a[i]; /* n */
printf("%d is %d\n",a[i],c[i]);
}
getch();
}
Ⅳ C語言中prime的作用
prime的作用就是判斷一個數是否為素數（也稱「質數」）。
例如：
#include<stdio.h>
intIsPrime(intn)
{
if(n<=1)return0;
if(n%2==0)returnn==2;
for(inti=3;;i+=2)
{
if(i>n/i)break;//等價於i*i>n,不用開方
if(n%i==0)return0;
}
return1;
}
intmain()
{
for(intn=100;n<=300;n++)
if(IsPrime(n))
printf("%4d",n);
return0;
}
(5)c語言貪心演算法擴展閱讀：
prime演算法
prime是以點為基礎出發進行檢索最小生成樹的一種貪心演算法。
思想：
將所有的點分成兩類，一類是已經放到碗里的，另一類是還沒有有放到碗里的，可以通過一個數組bool visit[]來記錄這個點到底是屬於第一類還是屬於第二類之後每一個周期索要進行的操作，找出一一定范圍內路徑的的范圍的最小值。
所有的從第一類點直接連接到第二類點的邊將最小的邊記錄下來（這個也就是生成樹中的一條邊）將這個新邊（這個一個連接第一類點和第二類點的邊）連到的那個第二類點歸類到第一類點中，之後重復這個操作，最終消滅所有的第二類點。
假設有n個節點，我最初給出一個點，以這個點開始進行搜索，這個時候該點為第一類點，其餘n-1個點為第二類點。之後進行n-1次操作，一共選出了n-1個邊（符合樹的性質），構成了最小生成樹。