while (2)

Report
418115: การโปรแกรมโครงสร้าง
คาสัง่ while (2)
ประมุข ขันเงิน
[email protected]
โปรแกรมเช็คจานวนเฉพาะ
 ให้ ผ้ ูใช้ ป้อนจำนวนเต็มบวกมำหนึ่งตัว
 แล้ วบอกว่ำมันเป็ นจำนวนเฉพำะหรือไม่
Enter n: 2
2 is a prime number.
Enter n: 7
7 is a prime number.
Enter n: 6
6 is not a prime number.
จานวนเฉพาะ
 จำนวนเฉพำะคืออะไร?
 จำนวนเต็มบวก (ฉะนั้นไม่นับ 0 หรือจำนวนเต็มลบ)
 ไม่ใช่จำนวนเต็มลบ
 แยกตัวประกอบไม่ได้
 กล่ำวคือ จำนวนเต็มบวกที่หำรมันลงตัวมีเพียงแค่สองตัว คือ 1 กับตัวมันเอง
 เช็คว่ำจำนวนเป็ นจำนวนเฉพำะได้ อย่ำงไร?
 สมมติว่ำจำนวนที่เรำต้ องกำรเช็คคือ n
 จำนวนที่หำรมันได้ มีแค่สองตัวคือ 1 กับ n
 ดังนั้น 2, 3, 4, …, n-1 ต้ องหำรมันไม่ลงตัว
 ฉะนั้นเรำเช็ค 2, 3, 4, …, n-1 ทีละตัวว่ำหำร n ลงตัวหรือไม่?
 มีสกั ตัวที่หำรลงตัว  ไม่ใช่จำนวนเฉพำะ
 ไม่มีสกั ตัวที่หำรลงตัว  เป็ นจำนวนเฉพำะ
ออกแบบโปรแกรม
 รับ n
 ตั้งลูปโดยใช้ k เป็ นตัวแปร counter
 k มีค่ำ 2 ถึง n-1
 สำหรับ k แต่ละค่ำเช็คว่ำ n % k == 0 หรือไม่?
 ถ้ ำใช่ ให้ จำไว้ ว่ำมีเลขหำรลงตัว
 หลังจำกลูปเสร็จกำรทำงำน ให้ ไปเช็คว่ำมีเลขหำรลงตัวหรือไม่
 ถ้ ำใช่ แสดงว่ำไม่เป็ นจำนวนเฉพำะ
 ถ้ ำไม่ใช่ แสดงว่ำเป็ นจำนวนเฉพำะ
ลูป
int is_prime = 1;
int k = 2;
while (k < n)
{
if (n % k == 0)
is_prime = 0;
k++;
}
ทัง้ โปรแกรม
#include <stdio.h>
int main()
{
int n;
printf("Enter n: ");
scanf("&d", &n);
int is_prime = 1;
int k = 2;
while (k < n) {
if (n % k == 0)
is_prime = 0;
k++;
}
if (is_prime && n != 1)
printf("%d is a prime number.\n", n);
else
printf("%d is not a prime number.\n", n);
return 0;
}
คาสัง่ break
 เคยเจอมำแล้ วในคำสั่ง switch
 สำมำรถใส่ไว้ ตรงในก็ได้ ในส่วนที่เป็ นคำสั่งที่ต้องกำรวนซำ้ ใน คำสั่ง while
 เมื่อเจอคำสั่ง break แล้ วลูป while จะเลิกกำรทำงำนทันที
 มักใช้ ควบคู่กบ
ั คำสั่ง if เสมอ
โปรแกรมเช็คจานวนเฉพาะ
 เรำไม่จำเป็ นต้ องให้ k มีค่ำตั้งแต่ 2 ถึง n-1 เสมอ
 ถ้ ำมีเลขสักตัวหำรลงตัว แสดงว่ำไม่ใช่จำนวนเฉพำะแล้ ว
ดังนั้นไม่มคี วำมจำเป็ นต้ องเช็คจำนวนอื่นอีก
 เรำต้ องกำรหยุดกำรทำงำนของลูปทันทีท่ี n%k == 0
 สำมำรถใช้ คำสั่ง break ได้ ในกรณีน้ ี
ลูปใหม่ทเี่ ร็วขึน้
int is_prime = 1;
int k = 2;
while (k < n)
{
if (n % k == 0)
{
is_prime = 0;
break;
}
k++;
}
โปรแกรมสาหรับแยกตัวประกอบ
 รับจำนวนเต็มหนึ่งตัวจำกผู้ใช้
 แยกตัวประกอบของจำนวนเต็มที่ผ้ ูใช้ ให้ มำ
Enter a positive integer: 128
128 = 2 * 2 * 2 * 2 * 2 * 2 * 2
Enter a positive integer: 365
365 = 5 * 73
Enter a positive integer: 97
97 = 97
การแยกตัวประกอบ
 แยกตัวประกอบคืออะไร?
 กำรเขียนจำนวนเต็มอยู่ในรูปผลคูณของจำนวนเฉพำะ
 ทำอย่ำงไรดีถงึ จะแยกได้
 สมมติว่ำเลขที่เรำต้ องกำรจะแยกตัวประกอบคือ n
 สมมติให้ n > 1 (กรณี n = 1 ไม่มีอะไร)
 หำจำนวนเฉพำะมำสักตัวที่หำร n ลงตัว
 สมมติว่ำจำนวนเฉพำะนี้คือ p
 ถ้ ำจำนวนเฉพำะนั้นหำร n ลงตัว เรำก็พิมพ์มัน
 แล้ วลบมันออกจำกตัวประกอบของ n ด้ วยกำรสั่ง n = n/p
การแยกตัวประกอบ
 48
 6
 หำร 2 ลงตัว
 หำร 2 ลงตัว
 48  24
63
 24
 3
 หำร 2 ลงตัว
 หำร 3 ลงตัว
 24  12
31
 12
 หำร 2 ลงตัว
 12  6
 จบกำรทำงำน
หาจานวนเฉพาะทีห่ าร n ลงตัว
 สมมติว่ำ n > 1
 ลองเปลี่ยนคำถำมเป็ นว่ำ
“จำนวนเฉพำะที่น้อยที่สดุ ที่หำร n ลงตัวคืออะไร?”
 สังเกต คำถำมนี้มค
ี ำตอบเดียวกับคำถำมที่ว่ำ
“จำนวนที่น้อยที่สดุ ที่มำกกว่ำ 1 ที่หำร n ลงตัวคืออะไร?”
หาจานวนเฉพาะทีห่ าร n ลงตัว
 ทำไม?
 สมมติว่ำ m เป็ นจำนวนที่น้อยที่สดุ ที่มำกกว่ำ 1 ที่หำร n ลงตัว
 สมมติอกี ว่ำ m ไม่ใช่จำนวนเฉพำะ
 แสดงว่ำ m ตัวแยกตัวประกอบได้ สมมติให้ p เป็ นจำนวนเฉพำะที่หำร m ลงตัว
 เรำรู้ว่ำ p < m และ p > 1
 แต่ p ก็หำร n ลงตัว
 ฉะนั้น m ไม่ใช่จำนวนที่น้อยที่สดุ ที่มำกกว่ำ 1 ที่หำร n ลงตัว
 เกิดข้ อขัดแย้ ง
หาจานวนเฉพาะทีห่ าร n ลงตัว
 หำจำนวนเฉพำะที่น้อยที่สดุ ที่หำร n ลงตัว
คือกำรหำจำนวนที่มำกกว่ำ 1 ที่น้อยที่สดุ ที่หำร n ลงตัว
 หำอย่ำงไร?
 เริ่มจำก p = 2
 เช็คว่ำ n%p == 0 หรือไม่?
 ถ้ ำใช่กจ็ บ
 ถ้ ำไม่ใช่กเ็ พิ่มค่ำ p ขึ้นหนึ่ง
หาจานวนเฉพาะทีห่ าร n ลงตัว
int p = 2;
while (n % p != 0)
p++;
ลูป
 หำ p หนึ่งตัวที่หำร n ลงตัว
 พิมพ์ p
 ลบ p ออกจำกควำมเป็ นตัวประกอบของ n
 n = n/p
 หยุดเมื่อไหร่ ?
 n == 1
ลูป
printf("%d = ", n);
while (n > 1)
{
int p = 2;
while (n % p != 0)
p++;
if (n/p==1)
printf("%d\n", p);
else
printf("%d * ", p);
n = n/p;
}
ทัง้ โปรแกรม
#include <stdio.h>
int main()
{
int n;
printf("Enter a positive integer: ");
scanf("&d", &n);
if (n == 1)
printf("1 = 1\n");
else {
printf("%d = ", n);
while (n > 1) {
int p = 2;
while (n % p != 0)
p++;
if (n/p==1)
printf("%d\n", p);
else
printf("%d * ", p);
n = n/p;
}
}
return 0;
}
เลขพาลินโดรม
 เลขพำลินโดรมคือเลขที่เขียนจำกหลังไปหน้ ำแล้ วมีค่ำเท่ำเดิม
 เช่น 12321 เป็ นเลขพำลินโดรม
 แต่ 123 ไม่ใช่ เพรำะ 123 ไม่เท่ำกับ 321
 สังเกตว่ำเลขพำลินโดรมจะต่อท้ ำยด้ วย 0 ไม่ได้
โปรแกรมตรวจสอบเลขพาลินโดรม
 อ่ำนจำนวนเต็มบวกจำกผู้ใช้ หนึ่งตัว
 ชนิด int
 ไม่เกิน 6 หลัก
 แล้ วบอกว่ำเลขนั้นเป็ นพำลินโดรมหรือไม่
Enter n: 12321
12321 is a palindrome
Enter n: 4567
4567 is not a palindrome
ออกแบบโปรแกรม
 พำลินโดรมคืออะไร?
 เขียนกลับหลังแล้ วได้ ตัวเติม
 จะทดสอบพำลินโดรมอย่ำงไร?
 ก็ลองเขียนกลับหลังดูแล้ วเทียบว่ำเท่ำกับตัวเดิมหรือไม่
เขียนกลับหลัง
 สมมติว่ำมีเลข n =123456
 สำมำรถเขียนกลับหลังโดยกำรมีเลขอีก 1 ตัว ตอนแรกเป็ น 0
 กระบวนกำร
 n = 123456
 n = 12345
 n = 1234
 n = 123
 n = 12
n=1
n=0
m=0
m=6
m = 65
m = 654
m = 6543
m = 65432
m = 654321
เขียนกลับหลัง
 ในแต่ละขั้น
 ดึงตัวหลังของ n ออกมำ
 เอำตัวหลังของ n ไปต่อท้ ำย m
 ลบตัวหลังออกจำก n
 กล่ำวคือ
int d = n % 10;
n = n / 10;
m = m*10 + d;
 หยุดเมื่อใด?
 เมื่อ n = 0
เขียนกลับหลัง
int m = 0;
while (n > 0)
{
int d = n % 10;
n = n / 10;
m = m*10 + d;
}
ทัง้ โปรแกรม
#include <stdio.h>
int main()
{
int n;
printf("Enter n: ");
scanf("%d", &n);
int nn = n;
int m = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
m = m*10 + d;
}
if (m == nn)
printf("%d is a palindrome\n", nn);
else
printf("%d is not a palindrome\n", nn);
return 0;
}
คาถาม
 ในจำนวนเต็มตั้งแต่ 1 ถึง 1,000,000 มีจำนวนเต็มกี่ตวั ที่เป็ นทั้ง
 จำนวนเฉพำะ และ
 พำลินโดรม?
 จำนวนเต็มเหล่ำนั้นคืออะไรบ้ ำง?
ออกแบบโปรแกรม
 เรำรู้วิธเี ช็คพำลินโดรม
 เรำรู้วธิ เี ช็คจำนวนเฉพำะ
 ฉะนั้นเอำจำนวนเต็มมำทีละตัวแล้ วเช็คว่ำมันเป็ นทั้งสองอย่ำงหรือไม่
 แล้ วก็นับจำนวนที่ใช่
ลูป
int n = 2;
while (n <= 999999)
{
[ตรวจว่า n เป็ นพาลินโดรมหรือไม่]
[ตรวจว่า n เป็ นจานวนเฉพาะหรือไม่]
[ถ้าใช่ท้ งั คู่พิมพ์ n]
}
ลูป (ฉบับเต็ม)
int n = 2;
while (n <= 999999) {
int m = 0;
int nn = n;
while (nn > 0) {
int d = nn % 10;
nn = nn / 10;
m = m*10 + d;
}
int is_palindrome = (m == n);
int is_prime = 1;
int k = 2;
while (k < n) {
if (n % k == 0) {
is_prime = 0;
break;
}
k++;
}
if (is_palindrome && is_prime)
printf("%d\n", n);
n++;
}
ปัญหา
 มันช้ ำ
 ทำไม?
 กำรเช็คจำนวนเฉพำะ
 ถ้ ำจะเช็คว่ำ 983,139 เป็ นจำนวนเฉพำะหรือไม่จะต้ องวนรอบทั้งหมดกี่รอบ?
 อำจจะถึง 983,137 รอบ!
 ฉะนั้นกรณีเลวสุดโปรแกรมจะต้ องวนรอบประมำณ 1,000,000 * 1,000,000
(แต่ควำมจริงน้ อยกว่ำนี้มำก)
ทาให้มนั เร็วขึน้ ?
 กำรเช็คจำนวนเฉพำะช้ ำ
 ต้ องพยำยำมหลีกเลี่ยง
 เรำสนใจเฉพำะเลขที่เป็ นทั้งพำลินโดรมและจำนวนเฉพำะ
 ดังนั้นถ้ ำเลขใดไม่เป็ นพำลินโดรมแล้ วเรำก็ไม่ต้องไปเช็คว่ำมันเป็ นจำนวนเฉพำะก็
ได้
คาสัง่ continue
 เมื่อสั่งแล้ วจะไปเริ่มต้ นลูปใหม่อกี ครั้งหนึ่ง
 ข้ ำมคำสั่งส่วนที่เหลือของลูปไป
 มักใช้ ควบคู่กบ
ั คำสั่ง if
หลีกเลีย่ งการเช็คจานวนเฉพาะ
int is_prime = 1;
int k = 2;
while (k < n) {
if (n % k == 0)
{
is_prime = 0;
break;
}
k++;
}
int n = 2;
while (n <= 999999) {
int m = 0;
int nn = n;
while (nn > 0) {
int d = nn % 10;
nn = nn / 10;
m = m*10 + d;
}
int is_palindrome = (m == n);
if (!is_palindrome) {
n++;
continue;
}
if (is_palindrome && is_prime)
printf("%d\n", n);
n++;
}

similar documents