4.2 นับ สะสม หาค่ามากสุด

โจทย์แข่งขันจำนวนมากให้ข้อมูลมาเป็นชุด บรรทัดแรกบอกว่ามีกี่ตัว แล้วตามด้วยตัวเลขทีละตัว เช่น คะแนนสอบของนักเรียน N คน อุณหภูมิ N วัน แล้วถามว่ารวมเท่าไร เฉลี่ยเท่าไร มีกี่คนที่ผ่าน ใครได้มากที่สุด ตอนนี้เรายังเก็บตัวเลขหลายตัวไว้พร้อมกันไม่ได้ (ต้องรอ array ในบทที่ 5) แต่โจทย์กลุ่มนี้ไม่ต้องเก็บ ใช้วิธี อ่านทีละตัว ใช้ทันที แล้วทิ้ง โดยมีตัวแปรสองสามตัวคอยจำสิ่งที่สรุปได้จนถึงตอนนั้น

สะสมผลรวม

ครูมีคะแนนสอบของนักเรียน N คน อยากรู้คะแนนรวม

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int total = 0; // (1)!
    for (int i = 1; i <= n; i++) {
        int score; // (2)!
        scanf("%d", &score);
        total += score; // (3)!
    }
    printf("total = %d\n", total);
    return 0;
}

1. ตัวแปรสะสมต้องตั้งค่าเริ่มต้นเป็น 0 ก่อนเข้าลูป เหมือนกดปุ่มล้างเครื่องคิดเลขก่อนเริ่มบวก
2. score เก็บแค่คะแนนของคนที่กำลังอ่านอยู่ รอบถัดไปก็ถูกค่าใหม่ทับ ไม่เป็นไร เพราะเราบวกเข้า total ไปแล้ว
3. เอาคะแนนคนนี้บวกเข้ากับผลรวมที่มีอยู่ ตรงนี้คือรูปแบบ x = x + ... ที่บทที่ 1 บอกว่าจะเจอบ่อย

5
70 85 90 62 48

total = 355

ข้อมูลเข้าจะวางบรรทัดเดียวหรือคนละบรรทัดก็ได้ scanf("%d") ข้ามช่องว่างและการขึ้นบรรทัดให้เองอยู่แล้ว ตามที่เห็นในหน้า 1.1

นับเฉพาะที่ตรงเงื่อนไข

ตัวนับคือตัวสะสมที่บวกทีละ 1 และบวกเฉพาะตอนที่เงื่อนไขเป็นจริง เอา if จากบทที่ 3 มาใส่ในลูป ทีนี้หาค่าเฉลี่ยและนับคนที่ได้ตั้งแต่ 50 คะแนนขึ้นไปพร้อมกัน

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int total = 0;
    int passed = 0;
    for (int i = 1; i <= n; i++) {
        int score;
        scanf("%d", &score);
        total += score;
        if (score >= 50) {
            passed++;
        }
    }
    printf("average = %.2f\n", (double)total / n);
    printf("passed = %d\n", passed);
    printf("failed = %d\n", n - passed);
    return 0;
}

6
70 85 49 62 48 50

average = 60.67
passed = 4
failed = 2

• ค่าเฉลี่ยต้องแปลงเป็น double ก่อนหาร ตามกับดักในหน้า 1.4 ถ้าหาร int ตรงๆ จะได้ 60
• ไม่ต้องนับคนตกแยก เพราะคนตกคือคนที่ไม่ผ่าน n - passed ได้เลย
• ข้อมูลชุดนี้ตั้งใจใส่ 49 กับ 50 ไว้ เพื่อตรวจว่า >= ถูก ถ้าเขียน > จะได้ passed เป็น 3 เวลาทดสอบโปรแกรมเอง ให้ลองค่าที่อยู่ตรงขอบเงื่อนไขเสมอ

หาค่ามากสุดและน้อยสุด

บันทึกอุณหภูมิสูงสุดของแต่ละวันไว้ N วัน วันไหนร้อนที่สุด วิธีคิดเหมือนเราดูตัวเลขทีละตัวด้วยตา จำตัวที่มากที่สุดเท่าที่เห็นมาไว้ในหัว เจอตัวใหม่ที่มากกว่าก็เปลี่ยนไปจำตัวใหม่ คำถามคือก่อนเห็นตัวเลขตัวแรก ควรจำค่าอะไรไว้ คำตอบที่ปลอดภัยที่สุดคือ ให้ตัวแรกเป็นค่าเริ่มต้น

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int first;
    scanf("%d", &first);
    int highest = first;
    int lowest = first;
    for (int day = 2; day <= n; day++) {
        int temp;
        scanf("%d", &temp);
        if (temp > highest) {
            highest = temp;
        }
        if (temp < lowest) {
            lowest = temp;
        }
    }
    printf("highest = %d\n", highest);
    printf("lowest = %d\n", lowest);
    return 0;
}

7
31 34 29 35 33 35 28

highest = 35
lowest = 28

อ่านวันแรกนอกลูป ลูปจึงเริ่มที่วันที่ 2 ถ้าโจทย์รับประกันว่า N อย่างน้อย 1 วิธีนี้ถูกเสมอ ไม่ว่าตัวเลขจะเป็นบวกหรือลบ

อีกวิธีที่เจอบ่อยคือเริ่มด้วยค่าที่น้อยกว่าทุกค่าที่เป็นไปได้ เช่น int highest = INT_MIN; จาก limits.h ที่เห็นในหน้า 1.3 ตัวเลขตัวแรกที่อ่านเข้ามาจะมากกว่าแน่นอน ใช้ได้เหมือนกัน แต่ต้องคิดให้ดีว่าค่าเริ่มต้นนั้นน้อยพอจริงไหม ส่วนลองทำให้พังท้ายหน้าจะเห็นว่าเริ่มด้วย 0 พังยังไง

จำว่าเป็นวันที่เท่าไรด้วย

โจทย์มักถามต่อว่าเกิดขึ้นวันไหน ให้มีตัวแปรอีกตัวจำวันไว้ เปลี่ยนพร้อมกับค่ามากสุดทุกครั้ง

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int highest;
    scanf("%d", &highest);
    int hot_day = 1;
    for (int day = 2; day <= n; day++) {
        int temp;
        scanf("%d", &temp);
        if (temp > highest) {
            highest = temp;
            hot_day = day;
        }
    }
    printf("hottest %d on day %d\n", highest, hot_day);
    return 0;
}

7
31 34 29 35 33 35 28

hottest 35 on day 4

35 องศาเกิดสองครั้ง วันที่ 4 กับวันที่ 6 โปรแกรมตอบวันที่ 4 เพราะ > เปลี่ยนค่าเฉพาะเมื่อเจอค่าที่มากกว่าจริงๆ ถ้าเปลี่ยนเป็น >= จะตอบวันที่ 6 แทน เพราะเท่ากันก็เปลี่ยน อ่านโจทย์ให้ดีว่าถามครั้งแรกหรือครั้งสุดท้าย แล้วเลือกเครื่องหมายให้ตรง

สะสมผลคูณ

สะสมผลคูณใช้หลักเดียวกับผลรวม ต่างกันตรงค่าเริ่มต้นต้องเป็น 1 ไม่ใช่ 0 เพราะอะไรคูณ 0 ก็ได้ 0 ตัวอย่างคือ แฟกทอเรียล (factorial) เขียนว่า n! คือ 1 × 2 × 3 × ... × n ใช้นับจำนวนวิธีเรียงของ n ชิ้น เช่น จัดเพื่อน 5 คนเข้าแถวได้ 5! = 120 แบบ

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    long long factorial = 1;
    for (int i = 1; i <= n; i++) {
        factorial *= i;
    }
    printf("%d! = %lld\n", n, factorial);
    return 0;
}

20

20! = 2432902008176640000

ผลคูณโตเร็วมาก 20! มี 19 หลักแล้ว ใกล้ขอบของ long long ที่ประมาณ 9 × 10¹⁸ ส่วน 21! เกินไปแล้ว ถ้าโจทย์ถามแฟกทอเรียลของเลขที่ใหญ่กว่านี้ มักให้ตอบเป็นเศษจากการหาร ซึ่งจะเรียนในบทที่ 12

ลองทำให้พัง

แบบที่ 1 ลืมตั้ง total = 0

ในโปรแกรม total แก้บรรทัดที่ 7 เป็น int total; เฉยๆ

กด F9 ใน Code::Blocks แล้วไม่มีคำเตือนเลย และบนเครื่องที่เขียนเอกสารนี้ยังพิมพ์ total = 355 ถูกด้วย เพราะบังเอิญหน่วยความจำตรงนั้นเป็น 0 อยู่ก่อน แต่ total เริ่มจากค่าขยะ ซึ่งจะเป็นอะไรก็ได้ เปลี่ยนเครื่องหรือเปลี่ยนโปรแกรมนิดเดียวก็ได้คำตอบผิด ถ้าคอมไพล์ด้วยตัวเลือก -O2 ที่สั่งให้ compiler ปรับโค้ดให้เร็วขึ้น compiler จะวิเคราะห์โค้ดละเอียดกว่าเดิม แล้วเตือนแบบนี้

total.c:11:15: warning: 'total' may be used uninitialized [-Wmaybe-uninitialized]
   11 |         total += score;
      |         ~~~~~~^~~~~~~~
total.c:7:9: note: 'total' was declared here
    7 |     int total;
      |         ^~~~~

บทเรียนคือ ได้คำตอบถูกบนเครื่องตัวเอง ไม่ได้แปลว่าโปรแกรมถูก ตัวแปรสะสม ตัวนับ ค่ามากสุด ต้องตั้งค่าเริ่มต้นเองทุกครั้ง

แบบที่ 2 เริ่มค่ามากสุดที่ 0

หลายคนเริ่ม highest ที่ 0 เพราะคิดว่าอุณหภูมิไม่ติดลบ แต่ถ้าเป็นอุณหภูมิช่องแช่แข็งของตู้เย็นล่ะ

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int highest = 0;
    for (int i = 1; i <= n; i++) {
        int temp;
        scanf("%d", &temp);
        if (temp > highest) {
            highest = temp;
        }
    }
    printf("highest = %d\n", highest);
    return 0;
}

4
-18 -20 -15 -19

highest = 0

คำตอบที่ถูกคือ -15 แต่ไม่มีค่าไหนมากกว่า 0 เลย highest จึงค้างอยู่ที่ 0 ซึ่งไม่ได้อยู่ในข้อมูลด้วยซ้ำ ชุดทดสอบของโจทย์ที่มีค่าติดลบได้มักมีชุดที่ติดลบทั้งหมดไว้ดักจุดนี้ ใช้วิธีให้ตัวแรกเป็นค่าเริ่มต้นแบบโปรแกรม hottest จะไม่พลาด

แบบที่ 3 แฟกทอเรียลใน int

#include <stdio.h>

int main()
{
    int factorial = 1;
    for (int i = 1; i <= 14; i++) {
        factorial *= i;
        printf("%d! = %d\n", i, factorial);
    }
    return 0;
}

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 1932053504
14! = 1278945280

ถึง 12! ยังถูก แต่ 13! จริงๆ คือ 6227020800 เกิน int ไปแล้ว ได้เลขที่ดูเหมือนปกติแต่ผิด และ 14! ยังน้อยกว่า 13! อีก ซึ่งเป็นไปไม่ได้ ลูปที่คูณสะสมทำให้ overflow ได้เร็วกว่าที่คิดมาก ก่อนเขียนให้ประมาณว่ารอบสุดท้ายผลจะใหญ่แค่ไหน ตามวิธีในหน้า 1.3

สรุป

• ข้อมูล N ตัวที่ใช้แค่ครั้งเดียว อ่านทีละตัวในลูป ใช้ทันที ไม่ต้องเก็บทุกตัว
• ผลรวมเริ่มที่ 0 ผลคูณเริ่มที่ 1 ตัวนับเริ่มที่ 0 ต้องตั้งเองทุกครั้ง Code::Blocks ไม่เตือนถ้าลืม
• นับตามเงื่อนไขคือใส่ if ในลูป แล้ว count++ เมื่อจริง
• ค่ามากสุดน้อยสุด ให้ค่าตัวแรกเป็นค่าเริ่มต้น อย่าเริ่มที่ 0
• > ได้ตำแหน่งแรกที่เจอ >= ได้ตำแหน่งสุดท้าย
• ผลรวมและผลคูณในลูปโตเร็ว ประมาณค่าสุดท้ายก่อนเลือก int หรือ long long