數(shù)的計(jì)數(shù)
Time Limit:1000MS Memory Limit:65536K
Total Submit:394 Accepted:183
Description
要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)（包括輸入的自然數(shù)n):
先輸入一個(gè)自然數(shù)n( n <= 1000),然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理：
（1）不作任何處理
（2）在它的左邊加上一個(gè)自然數(shù)，但該數(shù)不能超過原數(shù)的一半
（3）加上數(shù)后，繼續(xù)按此處理，直到不能再加自然數(shù)為止
Input
多個(gè)測試案例，每個(gè)測試案例
輸入一個(gè)自然數(shù)n
Output
輸出滿足以上條件的所有數(shù)的個(gè)數(shù)
Sample Input
6
Sample Output
6
Hint
對(duì)于6，滿足條件的數(shù)有
6
16
26
126
36
136
這個(gè)題目也貼一下，記得書上也有這么個(gè)習(xí)題的?。?br>代碼如下：
#include<string.h>
#include<stdio.h>
int main()
{
int s[1001];
int i,j,n;
memset(s,0,sizeof(s));
s[1]=1;
s[2]=2;
for(i=3;i<1001;i++)
{
for(j=1;j<=i/2;j++)
{
s[i]=s[j]+s[i];
}
s[i]++;
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",s[n]);
}
return 0;
}
在制作電路板時(shí)，要求將這n條線分布到若干個(gè)絕緣層上，在同一層上的連線不能相交。電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導(dǎo)線集Nets = ｛i，π(i)，1 ≤ i ≤ n｝的最大不想交子集。
書上解決這個(gè)問題的時(shí)候用了很多集合的概念，我花了一上午的時(shí)間去理解，結(jié)果沒理解啥意思！！！最后還是結(jié)合遞歸式和代碼看懂他說的最優(yōu)子結(jié)構(gòu)性質(zhì)這一段基本意思。。
定義了一個(gè)Size[i][j]二維數(shù)組，代表從上端點(diǎn)1，下端點(diǎn)1到上端點(diǎn)i，下端點(diǎn)j之間的最優(yōu)解。在這樣的定義下我們可以求得size[1][j],然后根據(jù)定義求得數(shù)組上其他值??！最后Size[n][n]就是所求解?。≡谶f推Size[i][j]時(shí)，要抓住i條線路在最優(yōu)解內(nèi)和不在最優(yōu)解內(nèi)做判斷。
代碼如下：
#include<windows.h>
#include<stdio.h>
#include<windef.h>
#include<string.h>
void MNS(int C[],int n,int size[][20])
{
int i,j;
for(j=0;j<C[1];j++) //初始化
{
size[1][j]=0;
}
for(j=C[1];j<=n;j++)//初始化
{
size[1][j]=1;
}
for(i=2;i<n;i++) //n>i>=2
{
for(j=0;j<C[i];j++) //j<C[i]時(shí)第i條線路必然不在最優(yōu)解內(nèi)
size[i][j]=size[i-1][j];
for(j=C[i];j<=n;j++)
size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1);//取第i條線路在最優(yōu)解內(nèi)和不在最優(yōu)解內(nèi)的較大值
}
size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1);//書上總喜歡把最后一項(xiàng)單獨(dú)計(jì)算.有時(shí)候是有問題的，就像0-1背包，雖然節(jié)約了時(shí)間
}
int Traceback(int C[],int size[][20],int n,int Net[])//構(gòu)造最優(yōu)解(從最后一項(xiàng)開始構(gòu)造)
{
int j=n,i;
int m=0;
for(i=n;i>1;i--) //1<i<=n
{
if(size[i][j]!=size[i-1][j]) //代表第i條入選
{
Net[m++]=i;
j=C[i]-1; //這里j的目的是為了構(gòu)造第一條線路是否入選，應(yīng)為i!=1
}
}
if(j>=C[1]) //入選
Net[m++]=1;
return m;
}
int main()
{
int C[20]={0,8,7,4,2,5,1,9,3,10,6},size[20][20],i,j,n,k;
int Net[20];
memset(size,0,sizeof(size));
memset(Net,0,sizeof(Net));
MNS(C,10,size);//構(gòu)造最優(yōu)解
printf("最優(yōu)解矩陣：\n");
n=10;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
printf("%d ",size[i][j]);
}
printf("\n");
}
k=Traceback(C,size,n,Net);
printf("最優(yōu)線路：\n");
for(i=0;i<k;i++)
printf("%d ",Net[i]);
printf("\n");
return 0;
}
運(yùn)行結(jié)果如下：
摘要: 工作的時(shí)候?qū)懙囊粋€(gè)修改記事本的程序段。記錄下代碼如下：
#include <windows.h>#include <stdio.h>#include <string.h>#include&...
閱讀全文
雖然說求最大值最小值函數(shù)在哪個(gè)頭文件下并不是非常重要，但是遇到問題的時(shí)候我們很快的找到~~ MSDN上說在algorithm下，但是出錯(cuò)了，其實(shí)這兩個(gè)函數(shù)需要包含兩個(gè)頭文件<windows.h>和<windef.h>文件，其他的還有__min和__max需要包含<stdlib.h>頭文件。。
#include <iostream>
#include <windows.h>
#include <stdio.h>
#include <windef.h>
using namespace std;
int main () {
cout << "max(1,2)==" << max(1,2) << endl;
cout << "max(2,1)==" << max(2,1) << endl;
cout << "max('a','z')==" << max('a','z') << endl;
cout << "max(3.14,2.72)==" << max(3.14,2.72) << endl;
cout << "max(1,2)==" << __max(1,2) << endl;
cout << "max(2,1)==" << __max(2,1) << endl;
cout << "max('a','z')==" << __max('a','z') << endl;
cout << "max(3.14,2.72)==" << __max(3.14,2.72) << endl;
return 0;
}
運(yùn)行結(jié)果如下：
posted @
2010-09-14 15:59 jince 閱讀(27722) |
評(píng)論 (4) |
編輯 收藏免費(fèi)餡餅
Time Limit:1000MS Memory Limit:65536K
Total Submit:615 Accepted:149
Description
都說天上不會(huì)掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說來gameboy的人品實(shí)在是太好了，這餡餅別處都不掉，就掉落在他身旁的10米范圍內(nèi)。餡餅如果掉在了地上當(dāng)然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側(cè)都不能站人，所以他只能在小徑上接。由于gameboy平時(shí)老呆在房間里玩游戲，雖然在游戲中是個(gè)身手敏捷的高手，但在現(xiàn)實(shí)中運(yùn)動(dòng)神經(jīng)特別遲鈍，每秒種只有在移動(dòng)不超過一米的范圍內(nèi)接住墜落的餡餅?，F(xiàn)在給這條小徑如圖標(biāo)上坐標(biāo)：
為了使問題簡化，假設(shè)在接下來的一段時(shí)間里，餡餅都掉落在0-10這11個(gè)位置。開始時(shí)gameboy站在5這個(gè)位置，因此在第一秒，他只能接到4,5,6這三個(gè)位置中期中一個(gè)位置上的餡餅。問gameboy最多可能接到多少個(gè)餡餅？（假設(shè)他的背包可以容納無窮多個(gè)餡餅）
Input
輸入數(shù)據(jù)有多組。每組數(shù)據(jù)的第一行為以正整數(shù)n(0 < n < 100000)，表示有n個(gè)餡餅掉在這條小徑上。在結(jié)下來的n行中，每行有兩個(gè)整數(shù)x,T(0 <= T < 100000),表示在第T秒有一個(gè)餡餅掉在x點(diǎn)上。同一秒鐘在同一點(diǎn)上可能掉下多個(gè)餡餅。n=0時(shí)輸入結(jié)束。
Output
每一組輸入數(shù)據(jù)對(duì)應(yīng)一行輸出。輸出一個(gè)整數(shù)m，表示gameboy最多可能接到m個(gè)餡餅。
提示：本題的輸入數(shù)據(jù)量比較大，建議用scanf讀入，用cin可能會(huì)超時(shí)。
Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0
Sample Output
4
Source
hdu1176
這個(gè)題目也屬于簡單的動(dòng)態(tài)規(guī)劃題目，如果直觀的從深度搜索的方法去做可能會(huì)超時(shí)，很多時(shí)候我們采用數(shù)組填表的方式求解，以空間換取時(shí)間??！
如果這個(gè)題目還有個(gè)小變化，就是撿餅人一開始站在5號(hào)位置，所以如果往我們直接從上往下求，只能求得最后每個(gè)點(diǎn)上的最優(yōu)值，所以我們應(yīng)該從后往前求，求得第一秒的時(shí)候每個(gè)點(diǎn)上的最優(yōu)值，也就是題目要求的解?。?br>代碼如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
int time[100001][11];
int max(int x,int y,int z)
{
if(x>y)
if(x>z)
return x;
else
return z;
else
if(y>z)
return y;
else
return z;
}
int main()
{
int i,j,k,n,x,y;
while(scanf("%d",&n)!=EOF&&n!=0)
{
memset(time,0,sizeof(time));
k=0;
for(i=0;i<n;i++)
{
scanf("%d %d",&y,&x);
time[x][y]++;
if(x>k)
k=x;
}
/**//* for(i=2;i<k'i++)
{
for(j=0;j<11;j++)
{
if(j>0&&j<10)
time[i][j]+=max(time[i-1][j-1],time[i-1][j],time[i-1][j+1]);
else if(j==0)
time[i][j]+=max(0,time[i-1][j],time[i-1][j+1]);
else
time[i][j]+=max(0,time[i-1][j-1],time[i-1][j]);
}
}*/
for(i=k-1;i>=0;i--)
{
for(j=0;j<11;j++)
{
if(j>0&&j<10)
time[i][j]+=max(time[i+1][j-1],time[i+1][j],time[i+1][j+1]);
else if(j==0)
time[i][j]+=max(0,time[i+1][j],time[i+1][j+1]);
else
time[i][j]+=max(0,time[i+1][j-1],time[i+1][j]);
}
}
printf("%d\n",time[0][5]);
}
return 0;
}
計(jì)算直線的交點(diǎn)數(shù)
Time Limit:1000MS Memory Limit:65536K
Total Submit:260 Accepted:119
Description
平面上有n條直線，且無三線共點(diǎn)，問這些直線能有多少種不同交點(diǎn)數(shù)。
比如,如果n=2,則可能的交點(diǎn)數(shù)量為0(平行)或者1(不平行)。
Input
輸入數(shù)據(jù)包含多個(gè)測試實(shí)例,每個(gè)測試實(shí)例占一行,每行包含一個(gè)正整數(shù)n（n <= 20）,n表示直線的數(shù)量.
Output
每個(gè)測試實(shí)例對(duì)應(yīng)一行輸出，從小到大列出所有相交方案，其中每個(gè)數(shù)為可能的交點(diǎn)數(shù),每行的整數(shù)之間用一個(gè)空格隔開。
Sample Input
2
3
Sample Output
0 1
0 2 3
Source
hdu1466
題目意思很明確，網(wǎng)上有很多的解釋都差不多，我記得從前我做這個(gè)題目的時(shí)候感到很糾結(jié)，主要還是看代碼的時(shí)候不容易看懂，現(xiàn)在稍微好一點(diǎn)了，總之一定要自己去畫，這樣才會(huì)理解！！
網(wǎng)上代碼如下（我再解釋一下）：
#include<stdio.h>
#include<string.h>
int main()
{
int i,j,n,f[21][191]; //f[i][j]代表i條直線是否能產(chǎn)生j個(gè)交點(diǎn)，如果能f[i][j]=1，否則為0；
memset(f,0,sizeof(f));
for(i=0;i<21;i++) //零個(gè)交點(diǎn)置零
f[i][0]=1;
for(n=2;n<21;n++) //從兩條直線開始求
for(i=n-1;i>=1;i--) //取出n-i條做變化
for(j=0;j<191;j++) //j變化
if(f[n-i][j]==1) //如果取出的n-i條能過產(chǎn)生j個(gè)交點(diǎn)，置f[n][j+(n-i)*i]=1，j+(n-i)*i為取出n-i條直線做變化情況下的交點(diǎn)數(shù)
f[n][j+(n-i)*i]=1;
while(scanf("%d",&n)!=EOF)
{
printf("0");
for(j=1;j<=n*(n-1)/2;j++) //統(tǒng)計(jì)
if(f[n][j])
printf(" %d",j);
printf("\n");
}
return 0;
}
其實(shí)可以直接這么寫，容易理解一點(diǎn)。。
代碼如下：
#include<string.h>
#include<stdio.h>
int main()
{
int i,j,n;
int f[21][191];
memset(f,0,sizeof(f));
for(i=1;i<21;i++)
f[i][0]=1;
for(j=1;j<191;j++)
f[1][j]=0;
for(n=2;n<21;n++)
{
for(i=1;i<n;i++)
{
for(j=0;j<191;j++)
{
if(f[i][j])
{
f[n][j+i*(n-i)]=1;
}
}
}
}
while(scanf("%d",&n)!=EOF)
{
printf("0");
for(j=1;j<=n*(n-1)/2;j++)
{
if(f[n][j])
printf(" %d",j);
}
printf("\n");
}
return 0;
}
C語言中的time：
代碼如下：
#include<stdio.h>
#include<time.h>
int main()
{
time_t timep;
time(&timep);
printf("%d\n",gmtime(&timep));
printf("%s\n",asctime(gmtime(&timep)));
printf("%s\n",ctime(&timep));
return 0;
}
數(shù)據(jù)字節(jié)數(shù)輸出：
代碼如下：
#include<stdio.h>
int main()
{
printf("char %d\n",sizeof(char));
printf("int %d\n",sizeof(int));
printf("short int %d\n",sizeof(short int));
printf("long int %d\n",sizeof(long int));
printf("float %d\n",sizeof(float));
printf("double %d\n",sizeof(double));
return 0;
}
printf輸出格式：
代碼如下：
#include<cstdio>
int main()
{
//for int
int i=30122121;
long i2=309095024;
short i3=30;
unsigned i4=2123453;
printf("%d,%o,%x,%X,%ld,%hd,%u\n",i,i,i,i,i2,i3,i4);//如果是：%l,%h，則輸不出結(jié)果
printf("%d,%ld\n",i,i2);//試驗(yàn)不出%ld和%d之間的差別，因?yàn)閘ong是4bytes
printf("%hd,%hd\n\n\n",i,i3);//試驗(yàn)了%hd和%d之間的差別，因?yàn)閟hort是2bytes
//for string and char
char ch1='d';
unsigned char ch2=160;
char *str="Hello everyone!";
printf("%c,%u,%s\n\n\n",ch1,ch2,str);//unsigned char超過128的沒有字符對(duì)應(yīng)
//for float and double,unsigned and signed can not be used with double and float
float fl=2.566545445F;//or 2.566545445f
double dl=265.5651445;
long double dl2=2.5654441454;
//%g沒有e格式，默認(rèn)6位包括小數(shù)點(diǎn)前面的數(shù),
//%f沒有e格式，默認(rèn)6位僅只小數(shù)點(diǎn)后面包含6位
//%e采用e格式，默認(rèn)6位為轉(zhuǎn)化后的小數(shù)點(diǎn)后面的6位
printf("%f,%e,%g,%.7f\n",fl,dl,dl,dl);
printf("%f,%E,%G,%f\n",fl,dl,dl,dl);//%F is wrong
printf("%.8f,%.10e\n",fl,dl);
printf("%.8e,%.10f\n\n\n",fl,dl);
//for point
int *iP=&i;
char *iP1=new char;
void *iP2;//dangerous!
printf("%p,%p,%p\n\n\n",iP,iP1,iP2);
//其他知識(shí)：負(fù)號(hào)，表示左對(duì)齊（默認(rèn)是右對(duì)齊）；%6.3，6表示寬度，3表示精度
char *s="Hello world!";
printf(":%s: \n:%10s: \n:%.10s: \n:%-10s: \n:%.15s: \n:%-15s: \n:%15.10s: \n:%-15.10s:\n\n\n",
s,s,s,s,s,s,s,s);
double ddd=563.908556444;
printf(":%g: \n:%10g: \n:%.10g: \n:%-10g: \n:%.15g: \n:%-15g: \n:%15.10g: \n:%-15.10g:\n\n\n",
ddd,ddd,ddd,ddd,ddd,ddd,ddd,ddd);
//還有一個(gè)特殊的格式%*.* ,這兩個(gè)星號(hào)的值分別由第二個(gè)和第三個(gè)參數(shù)的值指定
printf("%.*s \n", 8, "abcdefgggggg");
printf("%*.*f \n", 3,3, 1.25456f);
return 0;
}
去北京看奧運(yùn)
Time Limit:1000MS Memory Limit:65536K
Total Submit:398 Accepted:116
Description
2008年將到，王飛同學(xué)化了九牛二虎之力搞到了2張2008年奧運(yùn)會(huì)足球賽決賽的門票。真是開心??！他爸爸準(zhǔn)備開車跟他一起去北京看球賽。不過門票費(fèi)好貴啊，所以他爸爸說了，這個(gè)錢要在下學(xué)期的生活費(fèi)里扣（好摳門），不過如果他能讓從杭州去北京的油費(fèi)最?。ㄓ蛢r(jià)最近漲的好厲害?。敲淳筒豢凵钯M(fèi)了。
哈哈，這個(gè)就難不倒他了。在ACM里可不是白混的。
很快他算出了汽車從杭州到北京必須要加幾次油，并查出了到北京要經(jīng)過哪幾個(gè)城市，每個(gè)城市有哪些加油站以及從某城市各加油站到另一城市各加油站的距離和路況算出了各加油站之間的耗油量。
下面是不是很easy?
Input
有多個(gè)測試案例。第一行先輸入測試案例的數(shù)目T。
對(duì)于每個(gè)測試案例，第一行輸入一個(gè)整數(shù)n表示將在中途n（0 < n < 40)個(gè)城市中加油，后面緊跟著是n個(gè)整數(shù)代表每個(gè)城市有幾個(gè)加油站(每個(gè)城市加油站不超過10個(gè)）。
以下n+1行，每行由3個(gè)Si,Ej,L一組組成的好幾對(duì)整數(shù)，該行以0結(jié)束。表示從前一城市Si第i個(gè)加油站（杭州的話就是家拉）出發(fā)到該城市第j個(gè)加油站消耗的油量為L升。
Output
對(duì)于每個(gè)測試，輸出一行，內(nèi)容為最小總耗油量。
Sample Input
1
2 2 3
1 1 3 1 2 1 0
1 1 2 1 2 7 2 1 8 2 2 9 2 3 4 0
1 1 5 2 1 6 3 1 6 0
Sample Output
10
中文題，這種是最簡單的動(dòng)態(tài)規(guī)劃問題了，從左往右折，每次求得各個(gè)加油站上最小耗油量?。?！
看代碼的時(shí)候發(fā)現(xiàn)自己寫的看不懂了。。。。悲?。。?！代碼實(shí)現(xiàn)能力仍然是個(gè)話題?。。?/pre>
代碼如下：
#include<stdio.h>
#include<string.h>
int main()
{
int num1[50];
int num2[50]; //暫時(shí)存儲(chǔ)中間結(jié)果
int num3[50]; //結(jié)果數(shù)組
int t,n,k,s,e,i,g,m,j;
int l;
scanf("%d",&t); //組數(shù)
for(m=0;m<t;m++)
{
for(j=0;j<15;j++) //初始化num3
num3[j]=0;
scanf("%d",&n); //城市個(gè)數(shù)
for(i=0;i<n;i++) //城市加油站個(gè)數(shù)沒用。。。
scanf("%d",&k);
for(i=0;i<n+1;i++) //n個(gè)城市要走n步
{
for(j=0;j<15;j++) //初始化
num2[j]=1000000;
for(j=0;j<15;j++) //初始化
num1[j]=0;
while(scanf("%d",&g)!=EOF&&g!=0)//參數(shù)判定
{
s=g;
scanf("%d %d",&e,&l);
if(num2[e]==1000000)
{
num1[e]=num3[s]+l;
num2[e]=num1[e];
}
else if(num3[s]+l<=num2[e])
{
num1[e]=num3[s]+l;
num2[e]=num1[e];
}
}
for(j=0;j<50;j++) //結(jié)果存儲(chǔ)
num3[j]=num2[j];
}
printf("%d\n",num3[1]); //輸出結(jié)果
}
return 0;
}
學(xué)以致用?。?！
隨機(jī)數(shù)可以用來計(jì)算概率，面積等??！
一、隨機(jī)數(shù)，模擬拋硬幣正面時(shí)間頻率圖。
代碼如下：
#include<iostream>
#include<time.h>
using namespace std;
const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;
class RandomNumber
{
private:
unsigned long randSeed; //隨機(jī)種子
public:
RandomNumber(unsigned long s=0); //構(gòu)造函數(shù)，為randSeed置數(shù)
unsigned short Random(unsigned long n); //獲取0~n的一個(gè)隨機(jī)數(shù)
double fRandom(void); //獲取一個(gè)小數(shù)
};
RandomNumber::RandomNumber(unsigned long s)
{
if(s==0)
randSeed=time(0); //這里獲取直接用time函數(shù)獲取了一個(gè)時(shí)間值當(dāng)做種子了，沒有再用srand函數(shù)構(gòu)造種子了！網(wǎng)上查了下time()函數(shù)為從1970年1月1日0時(shí)0分0秒到此時(shí)的秒數(shù)?。?！
else
randSeed=s;
}
unsigned short RandomNumber::Random(unsigned long n)
{
// printf("randSeed:%lu \nmultiplier:%lu \nrandSeed*multiplier:%lu\n",randSeed,multiplier,randSeed*multiplier);
randSeed=multiplier*randSeed+adder; //這里存在一個(gè)越界問題，但是還是會(huì)從新獲得一個(gè)randSeed
// printf("(randSeed>>16):%lu\n",randSeed>>16);
return (unsigned short)((randSeed>>16)%n); //右移16為再與n取余，從而獲得一個(gè)0~n的隨機(jī)數(shù)，其實(shí)我還不明白，為啥還要右移呢？難道是為了隨機(jī)性？
}
double RandomNumber::fRandom(void)
{
return Random(maxshort)/double(maxshort);
}
int TossCoins(int numberCoins)
{
static RandomNumber coinToss; //注意了這里定義了一個(gè)靜態(tài)變量，在函數(shù)反復(fù)調(diào)用中coinToss的屬性值不變,從構(gòu)造函數(shù)的角度來理解，在函數(shù)反復(fù)調(diào)用過程中，該對(duì)象是不會(huì)重新去構(gòu)造的（不會(huì)重復(fù)調(diào)用構(gòu)造函數(shù)的）！
int i,tosses=0;
for(i=0;i<numberCoins;i++) //這里調(diào)用Random函數(shù)??！
{
tosses+=coinToss.Random(2); //返回0或1，1表示正面，0表示反面，累計(jì)正面朝上的次數(shù)
}
return tosses; //返回正面朝上的次數(shù)
}
void main()
{
const int NCOINS=10; //定義了常量，我從一些牛人哪里看到，我們應(yīng)該把靜態(tài)變量看成只讀。。。
const long NTOSSES=50000L;
long i,heads[NCOINS+1]; //h[i]代表NTOSSES次拋NCOINS次拋硬幣中i次正面次數(shù)，貌似有些拗口，按這個(gè)實(shí)例來說，應(yīng)該是做50000次拋10次硬幣，然后統(tǒng)計(jì)10次中出現(xiàn)0次正面朝上次數(shù)，1次正面朝上次數(shù)，。。10次正面朝上次數(shù)
int j,position;
for(j=0;j<NCOINS+1;j++)
heads[j]=0;
for(i=0;i<NTOSSES;i++) //累計(jì)
heads[TossCoins(NCOINS)]++;
cout<<"head結(jié)果:";
for(i=0;i<=NCOINS;i++) //輸出h結(jié)果
{
cout<<heads[i]<<" ";
}
cout<<endl;
for(i=0;i<=NCOINS;i++) //模擬拋硬幣正面事件平率圖
{
position=int (float(heads[i])/NTOSSES*100);//這里有強(qiáng)制類型轉(zhuǎn)換，其實(shí)這里計(jì)算了概率，通過強(qiáng)制類型轉(zhuǎn)換成整數(shù)！??！
cout<<i<<" ";
for(j=0;j<position-1;j++) //輸出空格
cout<<" ";
cout<<"*"<<endl;
}
}
運(yùn)行結(jié)果如下：
二、隨機(jī)數(shù)，計(jì)算∏?；舅枷胍彩沁\(yùn)用了概率事件！設(shè)有一個(gè)半徑為r的圓及其外切四邊形，向該圖形投擲N個(gè)點(diǎn)。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為K，由于投入的點(diǎn)在正方形上分布均勻，所以落入圓中的概率為∏*R^2/4/R^2，從投點(diǎn)的角度考慮，該概率為K/N，當(dāng)N足夠大時(shí)，我們可以近似的認(rèn)為二者相等。從而∏=4*K/N。
代碼如下：
double Darts(int n)
{
static RandomNumber dart;
int k=0;
for(int i=1;i<=n;i++)
{
double x=dart.fRandom();
double y=dart.fRandom();
if((x*x+y*y)<=1)
k++;
}
return 4*k/double(n);
}
當(dāng)n=500000000時(shí)，運(yùn)行結(jié)果如下：
printf輸出：
http://hi.baidu.com/jiaju111/blog/item/dcd7fd8ba9a7fa1ac9fc7ae2.htmlC語言時(shí)間日期函數(shù)說明：
http://www.cnblogs.com/neonlight/archive/2008/08/22/1273942.html
在別人眼里輕而易舉的的事情落在自己身上可能比登天還要難?。?br> 0-1背包問題：給定n中物品和一個(gè)背包。物品i的重量是wi，價(jià)值為vi，背包的容量為c。問如何選擇裝入背包中的武平，使得裝入背包中的物品價(jià)值最大？
書上有一行行的算式，證明最優(yōu)子結(jié)構(gòu)性質(zhì)和構(gòu)造遞歸關(guān)系。我沒怎么看明白最優(yōu)子結(jié)構(gòu)，但是我能看懂遞歸關(guān)系式！！我記得當(dāng)時(shí)老師叫我們的時(shí)候我自己想了好幾天才想明白這個(gè)遞歸式，但是始終覺得有點(diǎn)虛，借此我再寫一下！
設(shè)數(shù)組m(i,j)代表背包容量為j，可選物品為i，i+1，..n時(shí)的最優(yōu)解（這里的最優(yōu)解指的是選擇方案，并非正真的最優(yōu)值），顯然m(1,c)是0-1背包問題的解（
這里是書上的錯(cuò)誤，應(yīng)該是m[1]中的最大值！！我后來才發(fā)現(xiàn)的。。）。這種定義雖然比較拗口，但是還是可以接受的，其實(shí)我們也可以這么定義m[i][j],代表背包容量為j，當(dāng)前選擇物品為a[i]時(shí)的最優(yōu)解，顯然m數(shù)組中第n行的最大值是0-1背包問題的解??！
第一種定義的遞歸式如下：
0 1
m[i][j]=max{m[i+1][j],m[i+1][j-wi]+vi} j>=wi; m[i][j]=m(i+1,j) 0<=j<wi
第二種定義的遞歸式如下：
0 1 m[i][j]=max{m[i-1][j],m[i-1][j-wi]+vi} j>=wi; m[i][j]=m(i-1,j) 0<=j<wi
代碼如下：
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int max(int x,int y)
{
if(x>y)
return x;
return y;
}
int min(int x,int y)
{
if(x>y)
return y;
return x;
}
template <class Type>
void Knapsack(Type *v,int *w,int c,int n,Type m[][20])//構(gòu)造m，最優(yōu)取舍方案函數(shù)??！
{
int i,j;
int jMax=min(w[n]-1,c);
for(j=0;j<=jMax;j++)
m[n][j]=0;
for(j=w[n];j<=c;j++)
m[n][j]=v[n];
for(i=n-1;i>=1;i--)
{
jMax=min(w[i]-1,c);
for(j=0;j<jMax;j++)
m[i][j]=m[i+1][j];
for(j=w[i];j<=c;j++)
m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
/**//* m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);*///這里是書上的一個(gè)錯(cuò)誤，并不是m[1][c]就是0-1背包問題的解，事實(shí)上m[1]上的所有解都有可能??！
//所以還是應(yīng)該把m[1]上的所有最優(yōu)構(gòu)造都算出來，然后去最大值
}
template <class Type> //構(gòu)造x數(shù)組函數(shù)
void Traceback(Type m[][20],int *w,int c,int n,int x[])
{
int i;
for(i=1;i<n;i++)
{
if(m[i][c]==m[i+1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
}
x[n]=(m[n][c])?1:0;
}
int main()
{
int w[10],v[10],x[10],m[20][20],c,n,max,c0;
int i,j;
while(scanf("%d",&n)!=EOF)
{
max=0;
memset(m,0,sizeof(m));
for(i=1;i<=n;i++)
{
scanf("%d %d",&w[i],&v[i]);
}
scanf("%d",&c);
Knapsack(v,w,c,n,m); //構(gòu)造最優(yōu)取舍方案
for(i=1;i<=c;i++)
{
if(m[1][i]>max)
{
max=m[1][i];
c0=i;
}
}
Traceback(m,w,c0,n,x); //構(gòu)造x數(shù)組
printf("最優(yōu)矩陣如下：\n");
for(i=1;i<=n;i++)
{
for(j=0;j<=c;j++)
printf("%d ",m[i][j]);
printf("\n");
}
printf("方案如下：\n");
for(i=1;i<=n;i++)
printf("%d ",x[i]);
printf("\n");
}
return 0;
}
運(yùn)行結(jié)果如下：
第二種遞歸思路下的代碼和運(yùn)行過程我就不寫，就初始化和遞歸次序不同??！
我一個(gè)同學(xué)經(jīng)常跟我說，以后自己有孩子，一個(gè)賺了1000給我花100，一個(gè)賺了10000給我花200，我還是跟著賺1000的吧?。∑鋵?shí)問題不在別人，而在自己，努力就成?。?！我受益匪淺。。。