ปัญหาชิงรางวัลข้อที่ 19: 9-free numbers

[Mr.high]

ผมคิดว่าทักษะการเขียนโปรแกรมเป็นทักษะที่สำคัญนะครับ
มันอาจจะใช้คาดเดาคำตอบของปัญหาที่เรากำลังทำอยู่ได้นะ
ภาษาที่ผมแนะนำก็คือภาษา java คือรู้สึกว่าภาษา java เรียนรู้ได้ง่ายกว่าภาษา C
แต่ภาษา C ก็เป็นพื้นฐานที่ดี และ สอวน. คอม ก็เลือกภาษา C มาเป็นตัวที่ใช้เรียน
เท่าที่ได้ยินมารู้สึกว่าโปรแกรมที่ใช้เราใช้ในปัจจุบัน จะเขียนโดยภาษา C เป็นส่วนใหญ่ รองลงมาก็เป็น java (ถ้าผิดช่วยแก้ด้วยนะครับ)
ตอนนี้ผมเรียนที่จุฬา ที่นี่ภาควิชาคณิตศาสตร์ จะมีสองสาขา คือสาขาคณิตศาสตร์ กับ สาขาวิทยาการคอมพิวเตอร์
(ตอนนี้ผมเรียนสาชาคณิตศาสตร์นะครับ) ทำให้ผมเรียนวิชาทางสาชาคอมได้ง่ายพอสมควร
วิชาที่ผมแนะนำทางคอมพิวเตอร์ ก็คือ data structure and fundamental algorithm, algo design(ตัวนี้ยังไม่เคยเรียนนะ)
ผมคิดว่ามันน่าสนใจในไอเดีย และ เราสามารถนำมันมาประยุกต์ใช้ได้นะครับ

[warut]

ในทั้งหมด 20 ข้อที่ผมแปะมา ไม่มีข้อไหนจะทำให้ผมแปลกใจได้เท่ากับข้อนี้อีกแล้วครับ ผมเคยเข้าใจว่าคนที่สนใจคณิตศาสตร์จะชอบเขียนโปรแกรมด้วย เดาผิดอย่างแรงครับ (เอาตัวเองเป็นที่ตั้ง ) ผมทราบว่าการเรียนคณิตศาสตร์ในปัจจุบันไม่มีความเกี่ยวข้องกับการเขียนโปรแกรมเลย แต่ก็คิดไปเองว่าหลายๆคนคงชอบเขียนโปรแกรมเล่น

ผมเห็นด้วยกับความเห็นของคุณ Mr.high นะ ยกเว้นเรื่อง Java นี่ผมไม่รู้ แต่รู้สึกเหมือนว่าอะไรที่เขียนด้วย Java แล้วมักจะช้าครับ

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

วิธีการเขียนก็ง่ายๆครับ ไม่ต้องทำ optimization อะไรเลย อาศัยความเร็วของคอมพิวเตอร์ในยุคปัจจุบันก็พอแล้ว

เริ่มไล่จากเลข $ 1, 2, 3, \dots $ ไปทีละตัว ดูว่าตัวไหนเป็น 9-free บ้าง แล้วนับไปด้วยว่ามี 9-free กี่ตัว และที่ไม่ใช่ 9-free กี่ตัวแล้ว คอยเช็คดูว่ามีจุดไหนที่สองเซ็ตมีสมาชิกเท่ากันบ้าง

ส่วนการเช็คว่าจำนวนจำนวนหนึ่งเป็น 9-free มั้ย วิธีง่ายๆอันนึงก็คือเอา 10 ไปหาร เช็คดูว่าเศษเป็น 9 หรือไม่ ถ้าเป็นก็ไม่ใช่ 9-free ถ้าไม่เป็นก็มาดู quotient ถ้า quotient ไม่เท่ากับ 0 ก็วน loop กลับไปหารด้วย 10 ต่อ ถ้า quotient = 0 แล้วก็แสดงว่าเป็น 9-free ครับ

ยังมีใครอยากจะลองทำข้อนี้ไหมครับ??? ผมจะรอต่อไปอีกสักพักนึงนะ ถ้าไม่มีใครมาตอบผมก็เฉลยตัวเลข แล้วให้คุณ TOP ช่วยแปะตัวอย่างโปรแกรมเป็นภาษา C ด้วย

เฮ้อ ตอนแรกนึกว่าข้อนี้จะง่าย LaTeX ก็ไม่ต้องใช้ วิธีทำก็ไม่ต้องเขียน ไหงทำไปทำมาดูเหมือนว่าจะเป็นข้อแรกที่ผมต้องเฉลยเองซะงั้น

[M@gpie]

อ่า พอดี ช่วงที่พี่ warut โพสนี่ ติดงานหลายหลากทีเดียวครับ เลยไม่มีโอกาสเข้าร่วมแจม

ว่าด้วยเรื่องการเขียนโปรแกรมผมเจอการเขียนโปรแกรมแก้ปัญหา Optimization เข้าไปแล้วกลัวทีเดียวครับ 555 ค่อนข้างถึกทีเดียว ผมไม่ค่อยเก่งด้านเขียนโปรแกรมเท่าไร เน้นเอาให้ได้คำตอบก่อน

ส่วนข้อนี้ ผมขอเวลาตอนเย็นจะกลับมาลองทำดูละกันนะครับ แต่ขออนุญาตเป็น code ของโปรแกรม matlab จะได้ไหมเอ่ย ? แหะๆๆ คล้ายๆกับภาษาซีมากทีเดียว
ส่วนถ้าเกินวันนี้แล้วผมยังไม่โพสคำตอบก็เฉลยได้เลยครับ (คือคิดไม่ออกนั่นเอง)

[warut]

ภาษาอะไรก็ได้ ไม่มีเกี่ยงอยู่แล้วครับ

[Timestopper_STG]

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

อัพเดทล่าสุดรันถึง500ล้าน(ใช้เวลาทั้งสิ้นประมาณ7นาที)
9-free>>>291943040 9-เสียเงิน>>>208056960

[warut]

ข้อความเดิมของคุณ Timestopper_STG:
อัพเดทล่าสุดรันถึง500ล้าน(ใช้เวลาทั้งสิ้นประมาณ7นาที)
9-free>>>291943040 9-ไม่เสียเงิน>>>208056960

โปรแกรมของน้อง Timestopper_STG น่าจะมีที่ผิดแล้วล่ะครับ

[Timestopper_STG]

ผมไล่ตรวจดูทีละส่วนแต่ไม่พบที่ผิดอะครับแต่ลองแทนไปหลายเลข
ค่าที่ออกมามันก็ดูแปลกๆอยู่งั้นผมขอเอาโค้ดมาลงให้ตรวจไว้ชั่วคราวนะครับ
#include <stdio.h>
#include <conio.h>

int checkfreenum(int free,unsigned long num);

int findnum();

void main(){
findnum();
}

int checkfreenum(int free,unsigned long num){
int digit[20];
int n = 0;
while(num % 10 > 0){
digit[n] = num % 10;
if(digit[n] == free) return 0;
num /= 10;
}
return 1;
}

int findnum(){
unsigned long t = 0,f = 0;
int j = 0;
for(unsigned long i = 1; i <= 100000000; i++){
if(checkfreenum(9,i) == 1) t++;
else f++;
if((t != 0) && (t == f)){
++j;
printf("%u\n",i);
if(j == 13) return 0;
}
}
printf("%u %u\n",t,f);
return 0;
}

[TOP]

C Code:

1. #include <stdio.h>
2. #include <conio.h>
3.  
4. int checkfreenum(int free,unsigned long num);
5.  
6. int findnum();
7.  
8. void main(){
9.     findnum();
10. }
11.  
12. int checkfreenum(int free,unsigned long num){
13.     int digit[20];
14.     int n = 0;
15.     while(num % 10 > 0){
16.         digit[n] = num % 10;
17.         if(digit[n] == free) return 0;
18.         num /= 10;
19.     }
20.     return 1;
21. }
22.  
23. int findnum(){
24.     unsigned long t = 0,f = 0;
25.     int j = 0;
26.     for(unsigned long i = 1; i <= 100000000; i++){
27.         if(checkfreenum(9,i) == 1) t++;
28.         else f++;
29.         if((t != 0) && (t == f)){
30.             ++j;
31.             printf("%u\n",i);
32.             if(j == 13) return 0;
33.         }
34.     }
35.     printf("%u %u\n",t,f);
36.     return 0;
37. }

ฟังก์ชัน checkfreenum ยังทำงานไม่ถูกต้องครับ เพราะ ในกรณีที่ num หารด้วย 10 ลงตัว จะ return ค่า 1 กลับไปเสมอ ซึ่งไม่ถูกต้อง เช่น 90 ไม่ใช่ freenum แต่ฟังก์ชันนี้บอกว่าเป็น freenum

[Timestopper_STG]

ผิดง่ายๆอีกแล้วครับ ขอบคุณพี่Topอย่างแรงครับ
9565936
15588832
15588934
15633516
15943228
16263742
16263988
16264012
16297522
16305276
16305298
16305300
19131874
แก้เรียบร้อยละครับตอนแรกก็ตรวจแต่ตัวที่หลักเยอะๆที่แท้ผิดตัวแรก

[warut]

คำตอบยังมีที่ผิดนะครับ ใช้ cut & paste ไปเลยดีกว่าครับ ชัวร์ดี

[warut]

คำตอบอันที่แก้ไขแล้วถูกต้องครับ หลังจากรอมานาน 3 เดือนพอดิบพอดี น้อง Timestopper_STG ก็ได้เข้ามาช่วยจัดการข้อนี้ได้สำเร็จ และได้ไป 5 คะแนนครับ

ขอเชิญคุณ TOP ช่วยแปะตัวอย่าง C code ให้ชม พร้อมทั้ง comment (ถ้ามี) ด้วยครับ

[TOP]

C Code:

1. #include <stdio.h>
2. #include <string.h>
3. #include <limits.h>  /* For ULONG_MAX  Definition */
4.  
5. int isFreeNine(unsigned long ulNumber);
6.  
7. int main(int argc, char* argv[])
8. {
9.     unsigned long ulNumber;
10.     unsigned long ulNumNine = 0;
11.     unsigned long ulNumFreeNine = 0;
12.     unsigned long ulNumX;
13.  
14.     for(ulNumber = 1, ulNumX = 0; ulNumber <= ULONG_MAX && ulNumX < 13; ulNumber++)
15.     {
16.         if(isFreeNine(ulNumber) == 1)
17.             ulNumFreeNine++;
18.         else
19.             ulNumNine++;
20.  
21.         if(ulNumNine == ulNumFreeNine)
22.         {
23.             ulNumX++;
24.             printf("X[%lu] = %lu\n", ulNumX, ulNumber);
25.         }
26.  
27.     }
28.  
29.     return 0;
30. }
31.  
32. int isFreeNine(unsigned long ulNumber)
33. {
34.     char szNumber[10+1];
35.     int iIdx;
36.  
37.     sprintf(szNumber, "%lu", ulNumber);
38.  
39.     for(iIdx = strlen(szNumber)-1; iIdx >= 0; iIdx--)
40.     {
41.         if(szNumber[iIdx] == '9')
42.             return 0;
43.     }
44.  
45.     return 1;
46. }

สำหรับฟังก์ชัน isFreeNine เขียนตามที่คุณ warut แนะนำมาจะเป็นดังนี้

C Code:

1. int isFreeNine(unsigned long ulNumber)
2. {
3.     while(ulNumber > 0)
4.     {
5.         if(ulNumber%10 == 9)
6.             return 0;
7.         else
8.             ulNumber/=10;
9.     }
10.     return 1;
11. }

มีใครเคยทดลองเปลี่ยนจากเลข 9-free number เป็น เลขอื่นไหม เช่น 0-8 free number โดยหลักความเท่าเทียมกัน แล้วมันน่าจะกระจายตัวใกล้เคียงกัน แต่มันกลับไม่เป็นเช่นนั้น

ตัวอย่างผลลัพธ์ที่ได้ (อาจจะได้มากกว่านี้ เพราะผมให้เวลาในการรันโปรแกรมไม่นานนัก)

0-free number
X[1] = 10761678
X[2] = 14958584
X[3] = 14960718
X[4] = 14961734
X[5] = 15013206
X[6] = 15588832
X[7] = 15590574
X[8] = 15591958
X[9] = 15591960
X[10] = 15592032
X[11] = 15592228
X[12] = 15592230
X[13] = 15603696
X[14] = 15633494
X[15] = 15633504
X[16] = 15633516
X[17] = 16076088
X[18] = 16263742
X[19] = 20327616


1-free number
X[1] = 2
X[2] = 16
X[3] = 24
X[4] = 160
X[5] = 270
X[6] = 272
X[7] = 1456
X[8] = 3398
X[9] = 3418
X[10] = 3420
X[11] = 3422
X[12] = 13120
X[13] = 44686
X[14] = 118096
X[15] = 674934
X[16] = 1062880

2-free number
X[1] = 2
X[2] = 2914
X[3] = 3150
X[4] = 3152
X[5] = 3238
X[6] = 3398
X[7] = 26242
X[8] = 41558
X[9] = 42280
X[10] = 44686
X[11] = 236194
X[12] = 671784
X[13] = 672136
X[14] = 674910
X[15] = 674912
X[16] = 674926
X[17] = 674934
X[18] = 1299076
X[19] = 1305158
X[20] = 1305232
X[21] = 1305406
X[22] = 1325320
X[23] = 1346694
X[24] = 2125762

3-free number
X[1] = 39364
X[2] = 41288
X[3] = 41308
X[4] = 41558
X[5] = 43738
X[6] = 44686
X[7] = 354292
X[8] = 671782
X[9] = 671784
X[10] = 673594
X[11] = 674910
X[12] = 3188644


4-free number
X[1] = 472390
X[2] = 630226
X[3] = 642976
X[4] = 671782
X[5] = 671784
X[6] = 4251526


5-free number
X[1] = 590488
X[2] = 630224
X[3] = 630226
X[4] = 656098
X[5] = 671782
X[6] = 5314408


6-free number
X[1] = 6377290


7-free number
X[1] = 7440172
X[2] = 15633516
X[3] = 15633518
X[4] = 15707032
X[5] = 16264012
X[6] = 16271278
X[7] = 16305300
X[8] = 16307728
X[9] = 16308426
X[10] = 16308428
X[11] = 16769914
X[12] = 16935524
X[13] = 16937584
X[14] = 16938652
X[15] = 16938718
X[16] = 16938922
X[17] = 16979866
X[18] = 16980210
X[19] = 17006110


8-free number
X[1] = 8503054
X[2] = 15633516
X[3] = 15633518
X[4] = 15825130
X[5] = 16263742
X[6] = 16263826
X[7] = 16264012
X[8] = 16284400
X[9] = 16305276
X[10] = 16305278
X[11] = 16305280
X[12] = 16305300
X[13] = 16888012
X[14] = 16935524
X[15] = 18068992


9-free number
X[1] = 9565936
X[2] = 15588832
X[3] = 15588934
X[4] = 15633516
X[5] = 15943228
X[6] = 16263742
X[7] = 16263988
X[8] = 16264012
X[9] = 16297522
X[10] = 16305276
X[11] = 16305298
X[12] = 16305300
X[13] = 19131874

[Timestopper_STG]

ผมมีข้อสงสัยนิดนึงอะครับว่า#include<limits.h>มีไว้ทำอะไรหรอครับ

[TOP]

#include <limits.h>  /* For ULONG_MAX  Definition */

ตามที่ comment ไว้ครับ คือเพื่อให้อ้างถึงค่า ULONG_MAX ซึ่งเป็นค่ามากสุดของ unsigned long ได้

[warut]

เกี่ยวกับโจทย์ข้อนี้ ผมมีอีกคำถามนึงที่ผมลืมถามไปครับ

จะเห็นว่าอนุกรมของส่วนกลับของ 9-free numbers นั้น แม้จะลู่เข้าก็จริง แต่ลู่เข้าช้ามากๆ อีกทั้งลักษณะของอนุกรมยังไม่เอื้อต่อการใช้ analytical tools อีก ดังนั้นการหาผลบวกของอนุกรมนี้จึงเป็นเรื่องที่ยากมาก คำถามของผมคือ

ค่าประมาณของ ผลบวกของอนุกรมของส่วนกลับของ 9-free numbers ถูกต้องถึงทศนิยมตำแหน่งที่ 20 มีค่าเท่าใด

ผมให้ 3 คะแนนเลยสำหรับคำถามนี้ เพราะผมคิดว่าน่าจะหาข้อมูลยากสักหน่อยครับ