4.5 ลูปกับตัวเลขและเวลาที่ใช้

ในบทที่ 1 เราแยกหลักได้แค่เลขที่รู้จำนวนหลักล่วงหน้า มีลูปแล้วทำได้กับเลขกี่หลักก็ได้ หน้านี้รวมงานตัวเลขที่ออกสอบบ่อย คือ แยกหลัก กลับเลข หาตัวหาร และตรวจจำนวนเฉพาะ แล้วปิดท้ายด้วยเรื่องที่สำคัญพอๆ กับเขียนให้ถูก คือเขียนให้ทันเวลา เราจะจับเวลาลูปจริงบนเครื่อง แล้วใช้ตัวเลขนั้นตัดสินว่าวิธีไหนผ่านโจทย์ที่จำกัดเวลา 1 วินาที

แยกหลักทีละหลัก

หลักการเดิมจากหน้า 1.2 % 10 หยิบหลักขวาสุด / 10 ตัดหลักขวาสุดทิ้ง ทำซ้ำไปเรื่อยๆ จนเลขเหลือ 0 ก็ได้ครบทุกหลัก เราไม่รู้ล่วงหน้าว่าต้องวนกี่รอบ จึงใช้ while

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int digits = 0, digit_sum = 0;
    while (n > 0) {
        digit_sum += n % 10;
        digits++;
        n /= 10;
    }
    printf("digits = %d\n", digits);
    printf("sum = %d\n", digit_sum);
    return 0;
}

9075

digits = 4
sum = 21

ลูปได้หลักออกมาจากขวาไปซ้าย และทำให้ n กลายเป็น 0 ตอนจบ ถ้ายังต้องใช้เลขเดิมหลังลูป ให้เก็บสำเนาไว้ในตัวแปรอื่นก่อน ถ้าเลขใหญ่ถึง 10¹⁸ ก็ใช้วิธีเดียวกัน แค่เปลี่ยน n เป็น long long และรับด้วย %lld

เลข 0 มีกี่หลัก

ป้อน 0 ให้โปรแกรมข้างบน จะได้ digits = 0 เพราะเงื่อนไข 0 > 0 เป็นเท็จตั้งแต่แรก ลูปไม่ทำเลยสักรอบ แต่ 0 เขียนได้ด้วยหลักเดียว คำตอบที่ถูกคือ 1 นี่คืองานที่ต้องทำอย่างน้อยหนึ่งครั้ง ตรงกับ do while ในหน้า 4.1

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int digits = 0;
    do {
        digits++;
        n /= 10;
    } while (n > 0);
    printf("digits = %d\n", digits);
    return 0;
}

0

digits = 1

เลขอื่นที่ไม่ใช่ 0 ได้คำตอบเท่าเดิมทั้งสองแบบ ต่างกันแค่ 0 ตัวเดียว ชุดทดสอบชอบใส่ 0 ไว้ดักตรงนี้

กลับเลข

สร้างเลขใหม่จากหลักที่หยิบออกมา ทุกครั้งที่ได้หลักใหม่ เลื่อนเลขเดิมไปทางซ้ายหนึ่งหลักด้วยการคูณ 10 แล้วบวกหลักใหม่ต่อท้าย เลขที่อ่านกลับหลังแล้วได้เลขเดิม เช่น 12321 เรียกว่า palindrome

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int original = n;
    int reversed = 0;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    printf("reversed = %d\n", reversed);
    if (reversed == original) {
        printf("palindrome\n");
    } else {
        printf("not palindrome\n");
    }
    return 0;
}

12321

reversed = 12321
palindrome

ลองป้อน 1230 จะได้ reversed = 321 เพราะ 0 ที่ขึ้นหน้าไม่มีค่าเมื่อเป็นตัวเลข และต้องเก็บ original ไว้ก่อนเข้าลูปเพราะ n จะเหลือ 0

หาตัวหาร

ตัวหารของ n คือเลขที่หาร n ลงตัว วิธีตรงไปตรงมาคือลองทุกเลขตั้งแต่ 1 ถึง n แล้วดูว่า n % i เป็น 0 ไหม

#include <stdio.h>

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

36

1 2 3 4 6 9 12 18 36
count = 9

ใช้ count เป็นตัวบอกว่าพิมพ์ตัวแรกไปหรือยัง ตามวิธีพิมพ์คั่นด้วยช่องว่างในหน้า 4.1

ตรวจจำนวนเฉพาะ

จำนวนเฉพาะ (prime) คือจำนวนเต็มที่มากกว่า 1 และมีตัวหารแค่ 1 กับตัวมันเอง เช่น 2 3 5 7 11 ตรวจได้ด้วยการลองหารด้วย 2 ถึง n - 1 ถ้ามีตัวไหนหารลงตัวก็ไม่ใช่จำนวนเฉพาะ และเจอตัวเดียวก็พอ ใช้ break ได้เลย

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int smallest = 0;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            smallest = i;
            break;
        }
    }
    if (n < 2) {
        printf("%d is not prime\n", n);
    } else if (smallest == 0) {
        printf("%d is prime\n", n);
    } else {
        printf("%d is not prime, divisible by %d\n", n, smallest);
    }
    return 0;
}

91

91 is not prime, divisible by 7

smallest เป็นทั้ง flag และเก็บตัวหารที่เจอ ถ้ายังเป็น 0 แปลว่าไม่มีอะไรหารลงตัว ส่วนเงื่อนไข n < 2 แยกไว้เพราะ 0 กับ 1 ไม่ใช่จำนวนเฉพาะ แต่ลูปไม่ทำงานเลยสำหรับสองค่านี้ ถ้าไม่แยกจะตอบผิด

โปรแกรมนี้ถูก แต่ถ้า n เป็นจำนวนเฉพาะขนาดใหญ่ ลูปต้องวนเกือบ n รอบ เร็วพอไหม ต้องวัดดู

ลูปหนึ่งรอบใช้เวลาเท่าไร

โจทย์แข่งขันทุกข้อมีเวลาจำกัด ส่วนใหญ่ 1 วินาที ถ้าโปรแกรมทำงานนานกว่านั้น grader จะตัดจบแล้วให้ผล Time Limit Exceeded แม้คำตอบจะถูก เราจึงต้องรู้ว่าใน 1 วินาทีคอมพิวเตอร์ทำได้กี่รอบ วิธีที่ดีที่สุดคือจับเวลาเอง

ไลบรารี time.h มีฟังก์ชัน clock() ทำหน้าที่เหมือนนาฬิกาจับเวลา เรียกก่อนและหลังส่วนที่อยากวัด แล้วเอามาลบกัน หารด้วย CLOCKS_PER_SEC ก็ได้เป็นวินาที ชนิด clock_t คือชนิดของค่าที่ clock() ส่งกลับ ตอนนี้ใช้ตามแบบไปก่อนได้

#include <stdio.h>
#include <time.h>

int main()
{
    int n;
    scanf("%d", &n);
    clock_t start = clock();
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    clock_t end = clock();
    printf("sum = %lld\n", sum);
    printf("time = %.3f seconds\n", (double)(end - start) / CLOCKS_PER_SEC);
    return 0;
}

100000000

sum = 5000000050000000
time = 0.039 seconds

เวลาขึ้นกับเครื่อง ผลข้างบนวัดบนเครื่องที่เขียนเอกสารนี้ คือโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 ระบบ Windows 11 เสียบสายชาร์จและตั้งโหมดพลังงานเป็น Balanced คอมไพล์ด้วย GCC 14.2 ที่มากับ Code::Blocks วัดสองแบบ

• แบบ Code::Blocks กด F9 ตามปกติ ใช้ตัวเลือก -Wall อย่างเดียว compiler ไม่ได้ปรับโค้ดให้เร็ว
• แบบ -O2 เพิ่มตัวเลือก -O2 ที่สั่งให้ compiler ปรับโค้ดให้เร็วขึ้น ระบบตรวจของการแข่งขันมักคอมไพล์แบบนี้

รันแบบละ 5 ครั้ง ตารางนี้เป็นค่ากลางของ 5 ครั้งนั้น แถวที่เป็น n % i คือเปลี่ยนตัวลูปเป็น if (n % i == 0) count++; ซึ่งต้องหารทุกรอบ

อ่านตารางได้สามเรื่อง

1. บวก 10⁸ ครั้งใช้ไม่ถึงหนึ่งในยี่สิบวินาที บนเครื่องนี้ เวลาโตตามจำนวนรอบตรงๆ รอบเพิ่ม 10 เท่า เวลาก็เพิ่มราว 10 เท่า
2. งานในลูปมีผล การหาร (%) ช้ากว่าการบวกราว 3 ถึง 6 เท่า แบบ Code::Blocks ราว 3 เท่า แบบ -O2 ราว 6 เท่าเพราะลูปบวกเร็วขึ้นแต่ลูปหารไม่เร็วขึ้น ลูป 10⁹ รอบที่มีการหารเกิน 1 วินาทีไปแล้ว แม้บนโน้ตบุ๊กที่ค่อนข้างใหม่
3. -O2 ช่วยได้บางงาน ลูปบวกเร็วขึ้นเกือบเท่าตัว แต่ลูปที่มีการหารแทบไม่เปลี่ยน อย่าหวังให้ compiler ช่วยแก้วิธีที่ช้าเกินไป

ประมาณเวลาก่อนเขียน

เครื่องของ grader เป็นเครื่องอะไร เร็วแค่ไหน เราไม่รู้ และลูปในโจทย์จริงมักทำงานหลายอย่างต่อรอบ มากกว่าบวกเลขตัวเดียว จึงควรเผื่อไว้มากๆ หลักที่ใช้กันในวงการแข่งขันคือ

ตัวเลขนี้ตรงกับที่วัดได้ข้างบน 10⁸ รอบเหลือเวลาเผื่ออีกมาก ส่วน 10⁹ รอบที่มีการหารก็เกิน 1 วินาทีให้เห็นแล้ว วิธีใช้คือ ก่อนเขียนโค้ด ให้เอาขอบเขตในโจทย์มาคำนวณว่าลูปจะวนกี่รอบในกรณีที่แย่ที่สุด

ถ้าคำนวณแล้วไม่ทัน อย่าเพิ่งเขียน ให้หาวิธีที่วนน้อยลงก่อน เรื่องการประมาณเวลาแบบละเอียดจะเรียนในบทที่ 18

หาตัวหารให้เร็วขึ้น

ตัวหารมาเป็นคู่เสมอ ถ้า i หาร n ลงตัว n / i ก็หาร n ลงตัวด้วย เช่น 36 มีคู่ 1 กับ 36, 2 กับ 18, 3 กับ 12, 4 กับ 9 และ 6 กับ 6 ในแต่ละคู่ ตัวที่เล็กกว่าไม่มีทางเกิน √n เพราะถ้าทั้งสองตัวมากกว่า √n ผลคูณจะเกิน n จึงลองแค่ i ที่ i * i <= n แล้วนับทั้ง i และคู่ของมัน ระวังกรณีที่ i กับ n / i เป็นเลขเดียวกัน อย่างคู่ 6 กับ 6 ต้องนับครั้งเดียว

#include <stdio.h>

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

1000000000000

count = 169

n = 10¹² วิธีเดิมต้องวน 10¹² รอบ เทียบจากตารางข้างบนที่ลูปมีการหาร 10⁹ รอบใช้ราว 1.2 วินาที 10¹² รอบก็ราว 1200 วินาที หรือ 20 นาที วิธีนี้วนแค่ 10⁶ รอบ เสร็จทันที ตัวนับ i เป็น long long เพราะ n เกิน int และ i * i ต้องไม่ล้น

ตรวจจำนวนเฉพาะใช้เหตุผลเดียวกัน ถ้า n มีตัวหารอื่นนอกจาก 1 กับตัวเอง ต้องมีตัวหนึ่งที่ไม่เกิน √n แน่นอน ในโปรแกรม prime เปลี่ยนแค่บรรทัดที่ 8 เป็น

for (long long i = 2; i * i <= n; i++) {

จับเวลาลูปของโปรแกรม prime ทั้งสองแบบด้วย clock() บนเครื่องเดิม ป้อน 999999937 ซึ่งเป็นจำนวนเฉพาะ ลูปจึงวนจนสุดทาง ได้ค่ากลางของ 5 ครั้งดังนี้

0.000 ไม่ได้แปลว่าไม่ใช้เวลาเลย แต่น้อยกว่าที่ clock() วัดได้ แก้บรรทัดเดียว จากไม่ผ่านกลายเป็นผ่านสบาย นี่คือเหตุผลที่ต้องประมาณเวลาก่อนส่งทุกครั้ง

ลองทำให้พัง

แบบที่ 1 ลืมว่า 1 ไม่ใช่จำนวนเฉพาะ

ในโปรแกรม prime ตัดเงื่อนไข n < 2 ออก

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int smallest = 0;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            smallest = i;
            break;
        }
    }
    if (smallest == 0) {
        printf("%d is prime\n", n);
    } else {
        printf("%d is not prime, divisible by %d\n", n, smallest);
    }
    return 0;
}

1

1 is prime

n = 1 ลูปไม่ทำเลยเพราะ 2 < 1 เป็นเท็จ smallest ยังเป็น 0 โปรแกรมจึงสรุปว่าไม่มีตัวหาร ทั้งที่ 1 ไม่ใช่จำนวนเฉพาะตามนิยาม ชุดทดสอบเรื่องจำนวนเฉพาะแทบทุกโจทย์มี 1 อยู่ด้วย

แบบที่ 2 เริ่มลองหารที่ 0

ในโปรแกรม divisors เผลอเขียนลูปเริ่มที่ 0

for (int i = 0; i <= n; i++) {
    if (n % i == 0) {

คอมไพล์ผ่านไม่มีคำเตือน แต่รันแล้วโปรแกรมพังทันทีในรอบแรก เพราะ n % 0 คือหารด้วยศูนย์ Code::Blocks ขึ้นว่า

Process returned -1073741676 (0xC0000094)

เป็นรหัสเดียวกับหารด้วยศูนย์ในหน้า 1.2 ลูปที่ใช้ตัวนับเป็นตัวหาร ต้องเริ่มที่ 1 เสมอ

แบบที่ 3 i * i ล้น int

ถ้าในโปรแกรม prime เขียนเงื่อนไขเป็น i * i <= n แต่ i ยังเป็น int จะใช้ได้กับ n ทั่วไป แต่ลองป้อน 2147483647 ซึ่งเป็นค่ามากสุดของ int และเป็นจำนวนเฉพาะ

พอ i ถึง 46341 ค่า i * i เกิน int แล้วกลายเป็นค่าติดลบ ซึ่งน้อยกว่า n เสมอ ลูปจึงไม่หยุดที่ √n แต่วนต่อไปจนถึง n เอง บนเครื่องที่เขียนเอกสารนี้ ลูปใช้เวลาราว 2.8 วินาทีเมื่อจับด้วย clock() แล้วโปรแกรมพิมพ์ 2147483647 is not prime, divisible by 2147483647 ผิดทั้งเวลาและคำตอบ ประกาศ i เป็น long long แบบในหัวข้อก่อนหน้าจะไม่มีปัญหานี้

สรุป

• แยกหลัก ใช้ while (n > 0) กับ % 10 และ /= 10 ถ้าต้องนับ 0 เป็นหนึ่งหลัก ใช้ do while
• กลับเลข reversed = reversed * 10 + n % 10 และเก็บเลขเดิมไว้ก่อนถ้าต้องใช้
• จำนวนเฉพาะต้องมากกว่า 1 ลองหารตั้งแต่ 2 พอเจอตัวที่หารลงตัวก็ break
• บนเครื่องที่เขียนเอกสารนี้ บวก 10⁸ ครั้งใช้ 0.039 วินาที แต่ลูป 10⁹ รอบที่มีการหารใช้ 1.2 วินาที
• วางแผนด้วยหลัก 1 วินาที ทำได้ราว 10⁸ รอบ คำนวณจำนวนรอบจากขอบเขตโจทย์ก่อนเขียน
• ตัวหารมาเป็นคู่ ลองแค่ i * i <= n ก็พอ ลดจาก n รอบเหลือ √n รอบ

กลับเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด