一.概述
第二章主要是介紹了循環結構在程式中的使用,同時重點介紹了檔案操作(重點是通過檔案對資料的輸入輸出).參見這裡.
由于在算法比賽中對資料的輸入輸出有着嚴格的規定,是以如何正确有效地使用這些方法是我們需要注意和多加練習的地方.
二.例題分析
例題2-1涉及到了如何判斷整數的問題,可以參見這裡.
思路: 仍然是循環的使用,隻不過循環語句不是簡單語句,而是計算階層,是另外
一個循環,是以用二重循環就能解決了.
#include<stdio.h>
int main()
{
int s = 0,i,j,m,n;
scanf("%d",&n);
for(i = 1; i <= n; i++)
{
m = 1;
for(j = 1; j <= i; j++)
{
m *= j;
}
s += m;
}
printf("%d/n",s % 1000000);
return 0;
}
#include<stdio.h>
#include<time.h>
int main()
{
const int MOD = 1000000;
int i,j,n,m,s=0;
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
m = 1;
for(j = 1; j <= i ; j++)
m = (m * j % MOD);
s = (s + m) % MOD;
}
printf("%d/n",s);
printf("Time used = %.2lf/n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
由于上面的程式在n比較大的時候會産生溢出,得不出正确結果.是以改用另種方法.
這裡需要一點數學知識:要計算隻包含加法,減法和乘法的整數表達式除以正整數n
的餘數,可以在每步計算之後對n取餘,結果不變.
注意到這個程式用到了頭檔案time.h中的clock()函數.該函數傳回程式目前為止運作
的時間,這個時間除以常數CLOCKS_PRE_SEC_之後得到的值以"秒"為機關.
還需注意一點:常數CLOCKS_PER_SECC和作業系統相關,不要直接使用clock()的傳回值,
而應總是除以CLOCKS_PER_SEC.
并且clock() / CLOCKS_PER_SEC傳回的是從程式開始到結束的時間,也就是說輸入資料
的時間也被計算在内,顯然,這是我們不希望的.這裡可以用指令echo x | test echo
運用了"管道"的知識, 而x是輸入的資料,test是程式生成的可執行檔案名.
這樣就相當于系統自動地輸入資料,将手動輸入資料的時間造成的誤差排除了.
#include<stdio.h>
#define INF 1000000
int main()
{
int x,n,sum,min,max;
min = INF;
max = -INF;
sum = 0;
n = 0;
while(scanf("%d",&x) == 1)
{
if(x >= max)
max = x;
if(x <= min)
min = x;
sum += x;
n ++;
}
printf("%d %d %.3lf/n",min,max,(double)sum / n);
return 0;
}
分析:
1. 首先遇到的問題是:如何在沒給出輸入确定個數的變量的輸入問題.即不知道變量的個數,
就無法定義變量的确定名稱.
其實,就算知道了變量的個數,但是這個數量是很大的話,利用scanf來控制輸入也是不方
便的(當然,可以采取數組的形式).是以必須采用一種更加友善的方法.
就是 while(scanf("%d",&x)) 這種語句.由于scanf傳回值是int型,隻要有輸入傳回就是
成功的變量個數(不等于0).就不斷循環.當然,如果輸入完畢,可以人為結束:在windows下
先按enter确定輸入完畢,再按組合鍵Ctrl + Z,再按enter鍵确認.在linux下,按組合鍵
Ctrl + D;
2. 接下來的問題就是max和min的初值問題:一開始要設定max與min為什麼值才能與待輸入的
資料正确地比較呢?
一種比較直覺的方法是把max設為一個很小的值,把min設為一個很大的值.但是,這樣做有
一定的風險,因為你不能确定接下來輸入的資料到底有多大,或者有多小(本題中做了限制
是1000).比如你設min初值是1000.但是接下來輸入的資料都是比1000大的資料,那麼最小
值結果就是錯誤的.
另一種比較穩妥的方法是将max與min都賦予第一個輸入的資料的值,這樣,無論如何都不會
出現上面描述的那種情況了.但是程式要稍長一點.
#include<stdio.h>
int main()
{
double i;
for(i = 0; i != 0.2; i = i + 0.1)
printf("%.1lf/n", i);
return 0;
}
浮點數陷阱:
該程式的運作結果是: 無限循環.
之是以無限循環,那麼就可以推斷是for循環的條件始終成立,即 i 始終不等于10.
但是 i 是從0開始的,每次都自加0.1.那麼應該是100次後就停止.為什麼i始終不
等于10呢? 是因為浮點數的原因. 我們把10改成10.0,結果仍然是無限循環.
我們把 i += 0.1 改成 i++,發現執行10次後正常停止.我們可以初步推斷,是浮點數
的加法運算引起的.
接下來調用gdb輸出中間結果來觀察,發現 i 自加0.1後,并不是我們預想的等于0.1
而是等于 0.10000000000000001.
再往下執行幾次,i 的值分别是0.20000000000000001.
0.30000000000000004.
0.40000000000000002.
這樣,我們就了解了為什麼i 始終不等于10. 因為浮點數在進行小數運算的時候由于
精度問題,會有很小的誤差,然而用 = 或者 != 這樣的運算符來比較,是會檢測出這種
誤差的.是以導緻結果的不正确.
我們還可以多測試一下,将循環條件改為 i != 0.1 或者 i != 0.2時,程式能夠正常
運作,得到正常結果.但是當i != 0.3時,就是無限循環.顯然,在我們的程式中,這種
不确定的錯誤是不應該存在的.
是以,在定義循環變量時,盡量采用int型及整數的加減.因為循環的本質意義就是通過
各種條件來控制語句重複運作次數.而這個次數本身就是整數.要實作小數的功能盡量
通過循環中的語句來實作.
#define LOCAL
#include<stdio.h>
#include<math.h>
#include<time.h>
int main()
{
#ifdef LOCAL
freopen("c://data.in","r",stdin);
freopen("c://data.out","w",stdout);
#endif
int i,m,n,x = 0;
scanf("%d",&n);
m = floor(sqrt(n));
for(i = 1; i <= m; i++)
{
if(n % i == 0)
x++;
}
printf("%d/n",x * 2);
printf("Time used = %.2lf/n",(double)clock() / CLOCKS_PER_SEC);
return 0;
}
#include<stdio.h>
#include<math.h>
int main()
{
int n,i,m,x = 0;
scanf("%d",&n);
m = floor(sqrt(n));
for(i = 1; i <= m; i++)
{
if(n % i == 0)
x++;
}
printf("%d/n",x * 2);
return 0;
}
#include<stdio.h>
#include<math.h>
int main()
{
long long n,i,m,x = 0;
scanf("%I64d",&n);
m = floor(sqrt(n));
for(i = 1; i <= m; i++)
{
if(n % i == 0)
x++;
}
printf("%I64d/n",x * 2);
return 0;
}
分析:
第一個 重定向 + 計時版本,把前面的重定向檔案操作和計時函數聯系起來
第二個是 int型資料版本, 但是不能滿足n <= 10^12這個條件.可以通過上機實驗,
發現當輸入資料是10^9時,輸出是100,而增加到10^10時,輸出是44.明顯是資料溢出
造成程式結果不正确
第三個是 long long型資料版本,類型的容量可以達到10^19(略窄).就能滿足題目的
n <= 10^12 的條件了.注意此時的輸入輸出格式: %I64d. 但是在linux下的gcc和
vs2008都是使用%lld.
/*cstdio版本*/
/*
#include<cstdio>
using namespace std;
int main()
{
int a,b;
while(scanf("%d%d",&a,&b) == 2)
printf("%d /n",a+b);
return 0;
}
*/
/*iostream版本*/
/*
#include<iostream>
using namespace std;
int main()
{
int a,b;
while(cin >> a >> b)
cout << a+b << endl;
return 0;
}
*/
/*cin的輸入,fout的輸出*/
#include<fstream>
#include<iostream>
using namespace std;
//ifstream fin ("aplusb.in");
ofstream fout("aplusb.out");
int main()
{
int a,b;
while(cin >> a >> b)
fout << a + b << endl;
return 0;
}
分析:
上面的cstdio與原來的stdio.h版本的c程式無非就是前面加了c後面去掉了.h,并且多
了一條語句using namespace std;其他的差不多.
而後面的iostream版本輸入輸出明顯和原來的不一樣,改成了cin和cout.少去了格式控
制符的介入.
而cin和fout的混合使用也展現了c++能同時使用檔案流和标準輸入輸出流操作的友善,
顯然這樣比freopen的優勢就在于在程式中能同時使用标準輸入輸出了.
另:我在C-Free下編譯時,出現了錯誤,仔細尋找了下,發現是檔案名是.c為字尾的c檔案
編譯時就出錯,改成了.cpp為字尾後,錯誤就不存在了.不過我估計在其他編譯器中
不會出現這樣的情況.個例而已.
三.習題參考答案
/*習題2-1*/
/*重定向版
#include<stdio.h>
#define LOCAL
int main()
{
#ifdef LOCAL
freopen("2-1.in","r",stdin);
freopen("2-1.out","w",stdout);
#endif
int i,j = 0,n = 1;
scanf("%d",&i);
while(i / n)
{
n *= 10;
j ++;
}
printf("%d/n",j);
return 0;
}
*/
/*fopen版 c版本
#include<stdio.h>
int main()
{
FILE *fin, *fout;
fin = fopen("2-1.in","r");
fout = fopen("2-1.out","w");
int i,j = 0,n = 1;
fscanf(fin,"%d",&i);
while(i / n)
{
n *= 10;
j ++;
}
fprintf(fout,"%d/n",j);
fclose(fin);
fclose(fout);
return 0;
}
*/
/*fopen版本 c++版本*/
#include<fstream>
using namespace std;
ifstream fin("2-1.in");
ofstream fout("2-1.out");
int main()
{
int i,j = 0,n = 1;
cin >> i;
while(i / n)
{
n *= 10;
j ++;
}
cout << j << endl;
return 0;
}
/*習題2-2*/
/*注: 題目描述有點問題,應該是ABC = A^3 + B^3 +C^3 而不是 ABC = A^2 + B^2 + C^2*/
/*重定向版
#include<stdio.h>
#define LOCAL
int main()
{
#ifdef LOCAL
freopen("2-2.out","w",stdout);
#endif
int i,j,k,n,m;
for(i = 1; i <= 9; i++)
for(j = 0; j <= 9; j++)
for(k = 0; k <= 9; k++)
{
n = i*100 + j*10 + k;
m = i*i*i + j*j*j + k*k*k;
if(m == n)
printf("%d/n",n);
}
return 0;
}
*/
#include<stdio.h>
#define LOCAL
int main()
{
#ifdef LOCAL
freopen("2-2.out","w",stdout);
#endif
int i,j,k,n,m;
for(i = 1; i <= 9; i++)
for(j = 0; j <= 9; j++)
for(k = 0; k <= 9; k++)
{
n = i*100 + j*10 + k;
m = i*i*i + j*j*j + k*k*k;
if(m == n)
printf("%d/n",n);
}
return 0;
}
/*習題2-3*/
/*重定向版本
#include<stdio.h>
#define LOCAL
int main()
{
#ifdef LOCAL
freopen("2-3.in","r",stdin);
freopen("2-3.out","w",stdout);
#endif
int a,b,c,i;
scanf("%d%d%d",&a,&b,&c);
for(i = 10; i <= 100; i++)
{
if(i%3 == a && i%5 == b && i%7 == c)
{
printf("%d/n",i);
break;
}
}
if(i == 101)
printf("No answer/n");
return 0;
}
*/
/*fopen版本
#include<stdio.h>
int main()
{
FILE *fin,*fout;
fin = fopen("2-3.in","r");
fout = fopen("2-3.out","w");
int a,b,c,i;
fscanf(fin,"%d%d%d",&a,&b,&c);
for(i = 10; i <= 100; i++)
{
if(i%3 == a && i%5 == b && i%7 == c)
{
fprintf(fout,"%d/n",i);
break;
}
}
if(i == 101)
fprintf(fout,"No answer/n");
fclose(fin);
fclose(fout);
return 0;
}
*/
/*c++檔案流版本*/
#include<fstream>
using namespace std;
ifstream fin("2-3.in");
ofstream fout("2-3.out");
int main()
{
int a,b,c,i;
fin >> a >> b >> c;
for(i = 10; i <= 100; i++)
{
if(i%3 == a && i%5 == b && i%7 == c)
{
fout<< i << endl;
break;
}
}
if(i == 101)
fout << "No answer" << endl;
return 0;
}
/*習題2-4*/
/*重定向*/
#include<stdio.h>
#define LOCAL
int main()
{
#ifdef LOCAL
freopen("2-4.in","r",stdin);
freopen("2-4.out","w",stdout);
#endif
int n,i,j,k = 0;
scanf("%d",&n);
for(i = 0; i <= n; i++)
{
while(k < i)
{
printf(" ");
k++;
}
for(j = 1; j <= 2*(n-i)-1; j++)
{
printf("*");
}
printf("/n");
k = 0;
}
return 0;
}
#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("2-6.in");
ofstream fout("2-6.out");
int main()
{
int n,i;
double h = 0;
fin >> n;
for(i = 1; i <= n; i++)
{
h += (double)1/i ;
}
fout.precision(4);
fout << h;
return 0;
}
分析:
這裡使用的c++的檔案流進行檔案讀寫,将fout定義為ofstream流.但是這裡
有一個精度控制問題.
使用fout.precision()是能夠控制精度,但是控制的是整個數的有效位數.當整數
位是1位時,小數位是3位.但是當整數位是2位時,小數位就是2位了.
在網上查的資料都是使用cout怎麼樣控制的文章.setf(fixed)這樣是固定點方式
顯示,這種形式下控制的精度precision就是控制小數點後的精度了.但是在檔案流
中似乎不能這樣用.
/*習題2-7*/
#include<stdio.h>
#include<math.h>
#define LOCAL
int main()
{
#ifdef LOCAL
freopen("2-7.out","w",stdout);
#endif
double i = 1,x = 1,pi = 1;
int flag = -1;
while(fabs(x) >= pow(10,-6))
{
i += 2;
x = (double)1/(i);
pi += flag*x;
flag *= -1;
}
printf("%.8lf/n",pi);
printf("%.9lf/n",x);
return 0;
}
#include<stdio.h>
int main()
{
FILE *fin,*fout;
fin = fopen("2-9.in","r");
fout = fopen("2-9.out","w");
int a,b,c;
fscanf(fin,"%d%d%d",&a,&b,&c);
fprintf(fout,"%.*lf",c,(double)a/b);
return 0;
}
分析: 該題本身沒有難度,但是間接地給我們提供了printf的一種很強大的使用方法,
即通過變量來控制精度.我們一般在使用printf進行格式控制的時候,都是按照
給定的精度進行控制,比如精确到小數點後三位.而使用變量來控制精度呢?
在printf中可以使用類似于通配符的*來實作.
符号*是用後面參數表給出的變量進行替代.是以,%.*lf可通過與*對應的變量
來控制小數點後的位數.
剩下幾題沒有完美的解決方案,過段時間貼上來 :D
![GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)