『アルゴリズムコンテスト入門経典』第三章思考問題


タイトル1(必要なメモリ量)
配列は多くのデータを保存するために使用できますが、場合によってはデータを保存する必要はありません.次のテーマは配列を借りずに、配列を借りなければならないものですか?プログラミングして実装してください.入力は一度しか読めないと仮定します.1.数を入力し、数を統計します.2.最大値、最小値、平均数を求める数を入力します.3.最も近い数を入力します.4.いくつかの数を入力して、2番目に大きい値を求めます.5.いくつかの数を入力し、分散を求めます.6.平均数を超えない数を入力します.
コードは次のとおりです.
#include 
#include 

void count() // 1 
{
    int n, ct = 0;
    while(1 == scanf("%d", &n))
        ++ct;
    printf("You've inputted %d numbers
"
, ct); } void maxMinAverage() // 2 { int n, max, min, sum = 0, ct = 0, first = 1; while(1 == scanf("%d", &n)) { if(first) { max = min = n; first = 0; } if(max < n) max = n; if(n < min) min = n; sum += n; ++ct; } printf("max:%d min:%d average:%.3f
"
, max, min, sum*1.0/ct); } void nearest() // 3 { int nums[100], i = 0, j, k; while(1 == scanf("%d", &nums[i])) ++i; printf("%d
"
, i); int a = nums[0], b = nums[1], distance = abs(nums[0]-nums[1]); for(j = 0; j < i - 1; ++j) for(k = j + 1; k < i; ++k) if(abs(nums[j]-nums[k]) < distance) { distance = abs(nums[j]-nums[k]); a = nums[j]; b = nums[k]; } printf("two nearest numbers: %d %d, distance: %d
"
, a, b, distance); } void second() // 4 { int max, second, n; scanf("%d%d", &max, &second); int t1 = max > second ? max : second; int t2 = max < second ? max : second; max = t1; second = t2; //printf("max:%d second:%d
", max, second);
while(1 == scanf("%d", &n)) { if(n > max) { second = max; max = n; continue; } if(n > second && n != max) second = n; } printf("max:%d second:%d
"
, max, second); } void variance() // 5 { int nums[100]; int ct = 0, n, i; double ave = 0.0, sum = 0.0, psum = 0.0; while(1 == scanf("%d", &n)) { nums[ct++] = n; sum += n; } ave = sum / ct; for(i = 0; i < ct; ++i) psum += (nums[i] - ave) * (nums[i] - ave); printf("variance: %.3f
"
, psum / ct); } void smallerThanAve() // 6 { int nums[100]; int ct = 0, sct = 0, n, i; double ave = 0.0, sum = 0.0; while(1 == scanf("%d", &n)) { nums[ct++] = n; sum += n; } ave = sum / ct; for(i = 0; i < ct; ++i) if(nums[i] < ave) ++sct; printf("%d numbers smaller than average %f
"
, sct, ave); } int main() { //count(); //maxMinAverage(); //nearest(); //second(); //variance(); //smallerThanAve(); return 0; }

タイトル2(統計文字1の個数):
次のプログラムは、文字列の文字1の個数を統計することを意図していますが、残念ながら欠陥があります.
#include
#define maxn 10000000 + 10
int main()
{
    char s[maxn];
    scanf("%s", s);
    int tot = 0;
    for(int i = 0; i < strlen(s); i++)
        if(s[i] == 1) tot++;
    printf("%d
"
, tot); }

このプログラムには少なくとも3つの問題があり、そのうちの1つはプログラムが実行できなくなり、もう1つは結果が正しくなくなり、もう1つは効率が低下します.それらを見つけて修正できますか?
答え:
#include 

int main()
{
    int tot = 0;
    char ch;
    while((ch = getchar()) != EOF)
        if(ch == '1') ++tot;
    printf("%d
"
, tot); }