很簡單的題，還以為是高精度計算，完全沒必要。只是數字后面的0要消掉，不過oj似乎有問題，n=8時末尾0沒有消，有點扯淡啊。
#include<stdio.h>
char rs[][15] =
{
"0 1",
"1 2",
"2 2.5",
"3 2.666666667",
"4 2.708333333",
"5 2.716666667",
"6 2.718055556",
"7 2.718253968",
"8 2.718278770",
"9 2.718281526"
};
int main()
{
int i;
printf("n e\n");
printf("- -----------\n");
for(i = 0; i < 10; i++)
printf("%s\n", rs[i]);
//getchar();
}
/**//*int nn(int n)
{
int i, sum = 1;
for(i = 1; i <= n; i++)
sum *= i;
return sum;
}
double ii(int i)
{
return 1.0 / nn(i);
}
int main()
{
int i, j;
double e;
for(j = 0; j <= 9; j++)
{
e = 0.0;
for(i = 0; i <= j; i++)
{
e += ii(i);
}
printf("%d %.9lf\n", j, e);
}
getchar();
}*/
最簡單的方式就是先將結果按九位精度輸出，然后用字符串保存，輸出。注意二維字符數組的使用方式。
posted @
2012-02-22 18:07 小鼠標 閱讀(174) |
評論 (0) |
編輯 收藏
老鼠與貓咪做交易，貪心算法，不斷選取單價最便宜的購買即可
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000
typedef struct
{
float cm;
int j;
int f;
}JF;
int cmp( const void *a, const void *b)
{
JF *p = (JF *)a;
JF *q = (JF *)b;
if(p -> cm > q -> cm)
return 1;
else
return -1;
}
int main()
{
JF jf[1001];
float left, get;
int N;
int i, j;
scanf("%f%d", & left, & N);
while(N != -1)
{
for(i = 0; i < N; i++)//input && sort
{
scanf("%d%d", &jf[i].j, &jf[i].f);
if(jf[i].j != 0) //j為商品，f為單價。j==0時單價高到無窮
jf[i].cm = 1.0 * jf[i].f / jf[i].j;
else
jf[i].cm = MAX;
}
qsort(jf, N, sizeof(JF), cmp);
get = 0;//init
for(i = 0; i < N && left > 0.0; i++)//trade
{
if(left >= jf[i].f)
{
left -= jf[i].f;
get += jf[i].j;
}
else
{
get += jf[i].j * left / jf[i].f;
left = 0.0;
}
}
printf("%.3f\n", get);//out
scanf("%f%d", & left, & N);
}
}
。
1.需要注意的是邊界情況，j的輸入是可以為0的，這個時候可以將單價cm=f/j設為無窮大。
2.另外還要注意一些細節，結構體中將j、f設為int，cm為float，因此要將cm=1.0*f/j，否則cm的值會為0。
posted @
2012-02-19 21:56 小鼠標 閱讀(262) |
評論 (0) |
編輯 收藏前幾天自己寫了一個qsort函數，操作過程是選取第一個元素作為樞紐元，當時還為自己寫出了這個函數沾沾自喜，今天看了《數據結構與算法分析》中的快排分析才知道，我寫的代碼在極端情況下的時間復雜度為O(N^2)！說來慚愧啊，我立刻用了大小為十萬的已排序數組進行測試，結果不出所料，跟編譯器自帶的qsor函數效率就是天壤之別；當我用自己的排序函數對十萬個隨機數排序時效率就相差無幾了。哎，接著努力吧，小同志！
posted @
2011-08-22 16:00 小鼠標 閱讀(508) |
評論 (1) |
編輯 收藏
這一題不算難，確定最大值容易，掃描一遍數組即可得，時間復雜度是O(N)，結束的地方也好確定，隨著max更新就可以了。最難確定的是開始的界low，為此多花了不少冤枉時間！為了確定low，可以像確定high那樣再掃描一遍，不過這次要倒著掃描，從high開始，這兩個過程幾乎是對稱的。
#include<stdio.h>
#define M 100010
#define MIN 10000
int main()
{
int T,i;
scanf("%d",&T);
for(i=1;i<=T;i++)
{
int N,low,high;
long max=-MIN,partsum=0;
int num[M];
scanf("%d",&N);
int j;
for(j=0;j<N;j++)
scanf("%d",&num[j]);
for(j=0;j<N;j++)//正著掃描，確定上界high
{
partsum+=num[j];
if(partsum>max)
{
max=partsum;
high=j;
}
if(partsum<0)
{
partsum=0;
}
}
int partsum2=0,max2=-MIN;//這一遍倒過來掃描，確定下界low
for(j=high;j>=0;j--)
{
partsum2+=num[j];
if(partsum2>=max2)
{
max2=partsum2;
low=j;
}
if(partsum2<0)partsum2=0;
}
if(j==0)low=0;
printf("Case %d:\n",i);
printf("%d %d %d\n",max,low+1,high+1);
if(i!=T)printf("\n");
}
}
花了兩個多小時的時間，WA了5次，AC的那一刻實在很爽，相信這也是每個ACMer的原動力所在吧。
posted @
2011-08-19 21:56 小鼠標 閱讀(200) |
評論 (0) |
編輯 收藏
關于這道題我不想多說，水滴題，最快的方式就是調用qsort()函數了，一點技術含量都沒有。不過要是能自己寫出qsort()函數就不是那么隨意了。
這道題我做了兩遍，第一次是調用qsort庫函數，感覺不過癮，所以自己又寫了一遍qsort函數。
#include<stdio.h>
#define M 1010
int main()
{
void sort(int num[],int low,int high);
int T,N;
int num[M];
scanf("%d",&T);
while(T--)
{
int i,j;
scanf("%d",&N);
for(i=0;i<N;i++)
scanf("%d",&num[i]);
sort(num,0,N);
for(i=0;i<N-1;i++)
printf("%d ",num[i]);
printf("%d\n",num[i]);
}
}
void sort(int num[],int low,int high)
{
int po=low;//選取第一個元素為比較的初始值
int i=low,j=high,term;
if(high-low+1>=2)
{
while(i<=j)
{
for(;j>=i;j--)
{
if(num[j]<num[po])
{
term=num[po];
num[po]=num[j];
num[j]=term;
po=j--;
break;
}
}
for(;j>=i;i++)
{
if(num[i]>num[po])
{
term=num[po];
num[po]=num[i];
num[i]=term;
po=i++;
break;
}
}
}
sort(num,low,po-1);//遞歸調用
sort(num,po+1,high);
}
}
posted @
2011-08-19 16:48 小鼠標 閱讀(190) |
評論 (0) |
編輯 收藏進入學校實驗室也已有十八天，學長學姐都很熱心，知識講的不少，可這么多天過去了，就是感覺進步太小。今天又進行了一場比賽，八道題我只在最后30s時才搞定了一道，看看一起來的其他人，少則兩三道，多則四五道，我真是汗那！！
這樣下去也不是辦法，感覺整天都在跟著學長學姐們的步調走，而且還沒跟上，總感覺聽什么都很吃力。仔細想想，原來是沒有系統學習的緣故，前輩們講的固然很好，但都十分深奧，跳躍性強，什么動態規劃啊、最小生成樹啊、快速排序啊，雖然以后也一定要學，可對只剛學過C語言的人來說未免有些晦澀。當務之急最好找一本難度適宜的教材，從頭到尾看一遍，總比整天對著屏幕發呆好。
慢慢來吧，相信媛姐黨姐的水平將來我也會達到的，不急，畢竟一個月時間太短，學不了太多東西。最重要的是學會一種解題的思想，培養堅持的毅力，看著前輩們整天以刷題為樂，自己也仿佛若有所悟。正如黨姐第一節課所說的那樣：我來實驗室是為了什么，獎學金？證書？都不是，我們來這里是為了happy！
posted @
2011-08-15 19:45 小鼠標 閱讀(257) |
評論 (2) |
編輯 收藏最近花了五天時間把the C. programming language看了一遍，今天開始刷題。這道題講的是各處密鑰key和密文，已知加密公式，求出原文。題很水，只要把加密公式反過來就行了。
#include<stdio.h>
#include<string.h>
int main()
{
void changetonum(char ci[],int len);
void numtochar(char pl[],int len);
int i,j,k;
scanf("%d",&k);
while(k!=0)
{
char ci[100],pl[100];
int len;
scanf("%s",ci);
len=strlen(ci);
changetonum(ci,len);
for(i=0;i<len;i++)
{
pl[k*i%len]=(ci[i]+i)%28;
}
pl[i]='\0';
numtochar(pl,len);
puts(pl);
scanf("%d",&k);
}
}
void changetonum(char ci[],int len)
{ //該函數用于把密文轉化為數字
int i;
for(i=0;i<len;i++)
{
if(ci[i]>='a'&&ci[i]<='z')
{
ci[i]=ci[i]-'a'+1;
}
else if(ci[i]=='_')ci[i]=0;
else if(ci[i]=='.')ci[i]=27;
}
}
void numtochar(char pl[],int len)
{ //用于把解密后的數字轉化為原文
int i;
for(i=0;i<len;i++)
{
if(pl[i]>=1&&pl[i]<=26)pl[i]=pl[i]+'a'-1;
else if(pl[i]==0)pl[i]='_';
else if(pl[i]==27)pl[i]='.';
}
}
要特別注意的是一定要用一個變量len記錄原字符串長度，因為在轉換過程中可能會出現0（'_'對應的數字就是0），這樣的話調用strlen函數就無法得出正確的長度。
posted @
2011-08-13 16:14 小鼠標 閱讀(271) |
評論 (0) |
編輯 收藏