[มาตอบกันดูครับ]ปัญหานับเลขแบบ simple [Archive]

View Full Version : [มาตอบกันดูครับ]ปัญหานับเลขแบบ simple

retool2

03-12-2008, 11:55 PM

นานมาแล้วผมเจอปัญหาที่ simple อยู่ปัญหาหนึ่ง
แต่วิธีแก้มันไม่ง่ายอย่างคำถามเลย

ปัญหามีอยู่ว่า มีคนอยู่จำนวนหนึ่งยืนล้อมวงกันเป็นวงกลม
โดยทุกคนติดหลายเลขประจำตัวที่เสื้อ
คนที่ 1 จะเริ่มนับ 0 แล้วคนต่อไปจะนับ 1
คนต่อไปจะนับ 0 ไปเรื่อยๆ
คนที่นับ 0 จะต้องออกจากวง ส่วนคนที่นับ 1 จะอยู่ในวงต่อไป
คำถาม ?????
ถ้ามีคนอยู่ 500,000 คน คนที่ติดหมายเลขอะไรจะอยู่เป็นคนสุดท้าย

ลองคิดกันดูเล่นๆนะครับ
ความท้าทายอยู่ที่การหาคำตอบว่าเราจะหามันได้ยังไงครับ
(ผมใช้คอมพิวเตอร์ช่วยคำนวน หุหุ)

ผมอต้องการหาคำตอบเลยได้เขียนโปรแกรมขึ้นมาดังนี้
[hide=5][code]<html><body>
<form action="" method="post">
<table>
<TR><TD>Total people</TD><TD><input type="number" name="people"/></TD></TR>
<TR><TD>Start say</TD><TD><select name=startsay><option value ="0">0</option><option value ="1">1</option></select> 0 = out</TD></TR>
</table>
<input name="submit" type="submit" value="Count"/><input name="submit" type="submit" value="Count with print"/>
</form>
</body></html>
<?
if(isset($people) && $people<1){ ?>
<script language="Javascript">

</script>
<?
}else{

todsmatrix

04-12-2008, 12:00 AM

อยากนับเลขจัง
เดี๋ยวต้องไปโพสเยอะๆก่อน พอดีผมไม่ค่อยเก่ง เรื่องอธิบายนู้นนี่อ่า

chidkido

04-12-2008, 05:43 PM

**Hidden Content: Check the thread to see hidden data.**

retool2

04-12-2008, 06:46 PM

50000 อยู่ในช่วง 32768 แต่ไม่ถึง 65536
จึงตอบว่า 32768
[/b]
ยังไม่ถูกนะครับ
ถ้าเป็น 50,000 จะได้คนที่ 34,464 ครับ
ส่วน ถ้ามีทั้งหมด 500,000 คนที่อยู่คนสุดท้ายจะอยู่ระหว่างคนที่ 400,000 - 500,000 ครับ

xxxxy

04-12-2008, 09:58 PM

500000 ไม่ได้คับ เครื่องเน่า

[hide=2][code]
<?php
$ppls = 50000;

do{//สร้างคน

nena

05-12-2008, 02:52 AM

น่าทึ่งสุดๆ ตอนแรกเรานึกว่าจะเปนอะไรกวนๆ อ่านไปอ่านมาเริ่มรุสึกว่ามันไม่ใช่ล้อเล่น มาเจอคำตอบยิ่งแบบว่า ถ้าฉบับนมอุโด้ตต้องอุทานว่า แม่จ้าววววว มันสมองสุดยอดมากๆค่ะ

retool2

05-12-2008, 03:20 AM

<?php
$ppls = 50000;

do{//สร้างคน
$ppl_arr[] = ++$i; // เริ่มจาก 1
}while($i < $ppls);

while( $ppls != 1 ){
for($i =0; $i < $ppls; $i++){ //คนที่เหลือ
if($i % 2)
$new_arr[] = $ppl_arr[$i]; //เอาแต่คนที่นับ 1
}

$ppl_arr = $new_arr; //เอาคนที่เหลือ ไปนับใหม่
unset($new_arr);

$ppls = count($ppl_arr);
}

echo $ppl_arr[0]; //ผลลัพท์

//ปล. เครื่องผมทำ 500000 ไม่ได้อ่ะคับ เเออเร่อ
?>
[/b]
รู้สึกว่าวิธีเขียนแบบนี้จะไม่นับเป้นวงกลมนะครับ
เพราะว่าเท่าที่ดูคือ รู้ได้อย่างไรว่าคนสุดท้ายของการนับแต่ละรอบนับเลขอะไร
แล้วเริ่มใหม่แต่ละรอบนับเลขอะไร
เช่น นับ 100 คนควรจะออกมาเป็นแบบนี้

Total people = 100
Round 1 total people 100 count start with 0 and end with 1
People left => 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100
Round 2 total people 50 count start with 0 and end with 1
People left => 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 68 72 76 80 84 88 92 96 100
Round 3 total people 25 count start with 0 and end with 0
People left => 8 16 24 32 40 48 56 64 72 80 88 96
Round 4 total people 12 count start with 1 and end with 0
People left => 8 24 40 56 72 88
Round 5 total people 6 count start with 1 and end with 0
People left => 8 40 72
Round 6 total people 3 count start with 1 and end with 1
People left => 8 72
Round 7 total people 2 count start with 0 and end with 1
People left => 72

xxxxy

05-12-2008, 03:42 AM

โทษที ผมเข้าใจผิดเอง
อันนี้ แก้ให้ใหม่คับ
[code]<?php
$ppls = 50000;

do{//สร้างคน

retool2

06-12-2008, 05:25 PM

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

ขอบคุณคุณ xxxxy ด้วยนะครับที่เข้ามร่วมแสดงความคิด

thefoolly

06-12-2008, 06:37 PM

xxxxy

06-12-2008, 08:03 PM

ถ้า 500000 ยังสร้างอาเรย์ไม่ได้เลยคับ

Fatal error: Allowed memory size of 8388608 bytes exhausted (tried to allocate 35 bytes) in E:\WWW\test1\index.php on line 14

ตรงบรรทัด

$ppl_arr[] = ++$i;

retool2

06-12-2008, 10:19 PM

500000 หาร 2 ไปเรื่อย ๆ จนเหลือ 0
จะได้วงรอบ เอาวงรอบคูณ 2 ลบด้วย 500000
จะได้ตัวเลขสุดท้ายที่จะอยู่
ใช่รึเปล่าครับ เลขอะไรไม่รู้อ่ะครับ
ไม่มีความรู้ทางด้านการเขียนโปรแกรมเลยครับ
ไครรู้ช่วยทีซิ
[/b]
ยังไม่ใช่ครับ เพราะว่าถ้าหารไปเรื่อยๆมันจะมีเลขปลายๆที่หายไปครับ

ถ้า 500000 ยังสร้างอาเรย์ไม่ได้เลยคับ
Fatal error: Allowed memory size of 8388608 bytes exhausted (tried to allocate 35 bytes) in E:\WWW\test1\index.php on line 14
ตรงบรรทัด
$ppl_arr[] = ++$i;
[/b]
ที่ผมกำหนดให้ 500000 เพราะว่ามันจะได้ error นั่นแหละครับ

เทคนิกที่สองหาโดยไม่ต้องเขียนโปรแกรมสามารถทำได้ด้วยนะครับ
วางข้อมูลไว้เป็นสมการได้ ตัวอย่างเช่น
100 ตัว
รอบ 1 เริ่มนับ 0 เลขที่เหลือคือ 2n คนสุดท้ายนับ 1 เหลือทั้งหมด 100/2 = 50 คน
รอบ 2 เริ่มนับ 0 เลขที่เหลือคือ 4n คนสุดท้ายนับ 1 เหลือทั้งหมด 50/2 = 25 คน
รอบ 3 เริ่มนับ 0 เลขที่เหลือคือ 8n คนสุดท้ายนับ 0 เหลือทั้งหมด 25/2 ปัดลง = 12 คน
รอบ 4 เริ่มนับ 1 เลขที่เหลือคือ 8(2n-1) คนสุดท้ายนับ 0 เหลือทั้งหมด 12/2 = 6 คน
รอบ 5 เริ่มนับ 1 เลขที่เหลือคือ 8(2(2n-1)-1) คนสุดท้ายนับ 0 เหลือทั้งหมด 6/2 = 3 คน
รอบ 6 เริ่มนับ 1 เลขที่เหลือคือ 8(2(2(2n-1)-1)-1) คนสุดท้ายนับ 1 เหลือทั้งหมด 3/2 ปัดขึ้น = 2 คน
รอบ 7 เริ่มนับ 0 เลขที่เหลือคือ 8(2(2(2(2n)-1)-1)-1) คนสุดท้ายนับ 1 เหลือทั้งหมด 2/1 = 1 คน

เหลือ 1 คนแล้ว ใส่ค่า 1 ใน n จะได้คำตอบว่าเป็น 72 ครับ

คิดมือนี่เหนื่อยเหมือนกันนะเนี่ย ปัญหาง่ายๆแต่พอมาเป็นการคำนวนแล้วปวดหัวดีจริงๆ

Sparkz

07-12-2008, 12:25 AM

จากที่ผมใช้เวลา 20 นาทีมั่วออกมาได้ดังนี้

คนสุดท้ายคือ 262144 (ทำไมมีความรู้สึกว่าไม่น่าจะถูกก็ไม่รุ = =)

วิธีคิดของผม

**Hidden Content: Check the thread to see hidden data.**

ก็ได้ตามนั้นแหละครับ จะถูกมั๊ยล่ะเนี่ย = =

retool2

07-12-2008, 04:20 AM

จากที่ผมใช้เวลา 20 นาทีมั่วออกมาได้ดังนี้
คนสุดท้ายคือ 262144 (ทำไมมีความรู้สึกว่าไม่น่าจะถูกก็ไม่รุ = =)
ก็ได้ตามนั้นแหละครับ จะถูกมั๊ยล่ะเนี่ย = =
[/b]

ยังไม่ถูกครับ เพราะว่าสังเกตุที่การหักออกแต่ละครั้งนั้น
บางครั้งเหลือจำนวนคนเป็นจำนวนคี่ ทำให้การนับไม่ตรงแบบ 2^n ครับ

xxxxy

07-12-2008, 10:54 PM

Sparkz

08-12-2008, 10:51 AM

ยังไม่ถูกครับ เพราะว่าสังเกตุที่การหักออกแต่ละครั้งนั้น
บางครั้งเหลือจำนวนคนเป็นจำนวนคี่ ทำให้การนับไม่ตรงแบบ 2^n ครับ
[/b]

เพิ่งกลับไปอ่านโจทย์มาใหม่

สรุปแล้ว ลืมไปว่ายืนกันเป็นวงกลม = =

เด๋วไว้ว่างๆอีกทีค่อยคิดใหม่ = =

chidkido

08-12-2008, 04:27 PM

โอ้ย อ่านโจทย์ไม่ละเอียด ขอตอบใหม่อีกรอบ -_-
**Hidden Content: Check the thread to see hidden data.**
edit: แก้คำผิด

retool2

15-12-2008, 09:10 PM

ตอบคุณ retool2 นะครับ

คุณบอกเพื่อให้มันเออเร่อ ดังนั้น ผมจังไปแก้ที่ php.ini ตรงบรรทัด

memory_limit = 8M ; Maximum amount of memory a script may consume (8MB)

เปลี่ยนเป็น 50M

ดังนั้น คำตอบคือ

คนที่มีเบอร์ 475712 ครับ
[/b]
475712 เป็นคำตอบที่ถูกต้องครับ(ไม่รู้ว่าเครื่องคำนวนนานไหมนะครับ)
แต่ผมแนะนำเพิ่มเติมนะครับ ถ้าใครสังเหตุดีๆจะเห็นว่าถ้าเราใช้จำนวนคนเป็น
2 4 8 16 32 64 128 จะได้คำตอบออกมาเป็น 2 4 8 16 32 64 128
มันกลายเป็นลำดับทันทีเลยครับ ลองใส่ค่าคนเป็น 2 3 4 5 6 7 8 9 10 11 ... ถึงสัก 64
จะเริ่มเห็นความสัมพันธ์ครับ จะเห็นว่าความสัมพันธ์เป็นแบบ เพิ่มขึ้นทีละ 2 ไปเรื่อยๆ
จนมากกว่าจำนวนคน แล้วจากนั้นจะกลับไปเริ่มใหม่ที่ 2
ผมเลยเขียนโปรแกรมใหม่ หาได้เร็วขึ้นกว่าเดิมแต่หาได้แต่คำตอบ ไม่มีรายละเอียดแต่ละรอบเหมือนอันแรกดังนี้

Start with 0
and count 0 is out
input = : 500000 people.
answer = : 475712
Calculation time is 0.275274991989 seconds [/b] :D
[hide=5][code]
<body onload="document.people.people.focus();">
<form action="" method="post" name="people">
<input type="number" name="people"/>
<input name="submit" type="submit" value="Count"/>
</form>
Start with 0

and count 0 is out

<?php
if(!isset($people)){die();}
if($_POST['people']<=0 || !is_numeric($people)){die("Input must number only and more than 0");}
$time_start = microtime(true);
$answer = findlast($_POST['people']);
echo "input = : ".$_POST['people']." people.
";
echo "answer = : ".$answer."
";
$time_end = microtime(true);
$time = $time_end - $time_start;
echo "Calculation time is $time seconds\n";

function findlast($in){