สลากของอาณาจักรแมว

[opaaru]

ในการออกสลากของอาณาจักรแมว มีข้อกำหนดว่า จะออกรางวัลโดยใช้เลขเพียงสองตัว คือ เลขแปด (8) และ เลขเก้า (9) เท่านั้น และเลขที่จะถูกรางวัล คือ เลขที่มีค่าในฐาน 10 หารด้วย 2 ยกกำลังจำนวนหลักลงตัว ประชาชนแมวของเมืองนั้นต้องการได้สลากที่ถูกรางวัล ท่านก็สามารถเข้าร่วมได้ในฐานะแขกรับเชิญของอาณาจักรนี้ ท่านจะซื้อสลากหมายเลขใดจึงจะถูกรางวัล จงหา f(x) เมื่อ x คือจำนวนหลัก f(x) คือ เลขสลากที่ถูกรางวัล
เช่น 4 หลัก เลขที่ถูกรางวัลคือ 9888

ขอขอบคุณล่วงหน้าสำหรับคำตอบครับ

[warut]

สำหรับคำตอบข้อนี้เท่าที่ผมทราบเราไม่สามารถเขียน f(x) เป็น explicit form ได้นะครับ
แต่เราสามารถเขียนเป็นแบบ recurrence ได้ คือเขียน f(x) ในรูปของ f(x-1) ถ้าผมว่าง
จะมาพิมพ์วิธีคิดให้ ว่าแต่ได้โจทย์ข้อนี้มาจากไหนอะครับ

[opaaru]

จริงๆแล้วมันเป็นโจทย์ปัญหาให้เขียนโปรแกรมของคอมนะครับ ต้นฉบับอยู่ที่คลิกที่นี่

[ToT]

ไปแข่งมาด้วยหรอครับ ห่ะๆๆ
ถ้าให้หา f(x) วิธีที่ง่ายที่สุดก้อคือ ให้โปรแกรมรับค่า x มาแล้วคำนวณหาค่าตัวหารก่อน หลังจากนั้น ให้โปรแกรม loop หาค่าตัวตั้งทั้งหมดที่เป็นไปได้ตามจำนวนหลัก เช่น x=3 ตัวตั้งที่เป็นไปได้ทั้งหมดคือ ...
888
889
898
899
988
989
998
999

ตรงนี้ก้อคง loop สลับเลขเอา ใช้อาเรย์เก็บค่าเลข 8,9 แล้วค่อยเอามาเปลี่ยนเป็น long เอาไปหารกับตัวหารที่คำนวณไว้แล้วอีกที ถ้าไม่มีตัวใดหารลงตัวเลย ---> ไม่มีคำตอบ

แต่ถ้าหมายถึงให้หา function f ทำไม่เปงเหมือนกัน ...

[TOP]

สำหรับผลเฉลยแบบ Recursive คือ

f(x+1) =

์ ํ ๎

8*10x + f(x) 9*10x + f(x)

เมื่อ 2x+1 | f(x) เมื่อ 2x+1 หาร f(x) ไม่ลงตัว

กรณีแรก พิจารณาไม่ยาก เนื่องจาก 2^x+1 | 8*10^x อยู่แล้ว ดังนั้นหาก 2^x+1 | f(x) จะได้ 2^x+1 | 8*10^x + f(x)

กรณีที่สอง หาก 2^x+1 หาร f(x) ไม่ลงตัว จะเหลือเศษเหลือเป็น 2^x เสมอ (เราจะเห็นเศษเหลือชัดเจน หากลองเปลี่ยน f(x) ให้เป็นเลขฐานสอง ซึ่งจะมีศูนย์ต่อท้ายจำนวน x ตัว ดังนั้นเศษเหลือจากการหารด้วย 2^x+1 จึงได้จากการเลื่อนบิตไปทางขวา x+1 หลัก ได้เศษเหลือเป็น 2^x) พิจารณาในทำนองเดียวกัน จะได้ 2^x+1 หาร 9*10^x ไม่ลงตัว และเหลือเศษเป็น 2^x เสมอ ดังนั้น 2^x+1 | 9*10^x + f(x)