ปัญหาจากโจทย์นะครับ การหาคนที่ดังที่สุดในงานเลี้ยง ตอนนี้เราเรียกว่า red hot problem หรือ superstar problem ในงานสังคม เราจะเรียกคนที่ใครๆที่มาก็รู้จัก แต่เจ้าตัวไม่รู้จักคนอื่นเลยเรียกว่า Celebrity หรือ Super star หรือบุคคลที่ hot ที่สุด ปัญหาคือมีคน n คน ในงานเลี้ยงแล้วเราอยากทราบว่าใครเป็นดาราของงานนี้ ให้หาว่าใครเป็น celebrity
แต่ผมหาอัลกอริทึมวิธีแก้ปัญหานี้ได้ใน Google เป็นอัลกอริทึมแบบแบ่งแยกฝั่งซ้ายขวา เพื่อหาคนที่รู้จักกัน แล้วหาค่ามาแต่ก็ยังไม่เข้าใจอยู่ดีว่ามันเข้ากับ Code ที่หามาได้(ข้างล่าง) ผลที่รันออกมาได้เท่ากับ Celebrity Found:2
-----------------------------------------------------------------------------------
package test;
public class CelebrityFinding{
// people numbered from 0 to 3;
static final int SIZE = 4;
public static void main(String[] args) {
int celeb = findCandidate();
if (checkIfCelebrity(celeb)) {
System.out.println("Celebrity found: " + celeb);
} else
System.out.println("Celebrity not found");
}
static int findCandidate() {
int celeb = 0;
for (int i = 1; i < SIZE; i++) {
// if celeb knows i, celeb can't be the candidate.
if (haveAcquaintance(celeb, i)) {
celeb = i;
}
}
return celeb;
}
static boolean checkIfCelebrity(int celeb) {
for (int i = 0; i < SIZE; i++) {
// check if the celebrity knows noone and everyone knows the
// celebrity.
if ((celeb != i)
&& (!haveAcquaintance(i, celeb) || haveAcquaintance(celeb,
i))) {
return false;
}
}
return true;
}
static boolean haveAcquaintance(int a, int b) {
// assuming valid input
int[][] input = { {0,0,1,1},{0,0,1,0},{0,0,0,0},{0,0,1,0} };
return input[a]
== 1 ? true : false;
}
}
-------------------------------------------------------------------------------------------------
เลยอยากให้ช่วยอธิบายอัลกอริทึมให้เข้าใจหน่อย หรือว่า ถ้า Code หรืออัลกอริทึมผิดตรงไหนช่วยบอกหรือวิธีแก้ไขให้หน่อยนะครับ จะเป็นพระคุณอย่างสูง ขอบคุณครับ
ปล.มันคือ Binary Search ใช่หรือป่าวครับ???
ปัญหา Celebrity Problem ช่วยหน่อยครับ ยัง งง กับมันอยู่
แต่ผมหาอัลกอริทึมวิธีแก้ปัญหานี้ได้ใน Google เป็นอัลกอริทึมแบบแบ่งแยกฝั่งซ้ายขวา เพื่อหาคนที่รู้จักกัน แล้วหาค่ามาแต่ก็ยังไม่เข้าใจอยู่ดีว่ามันเข้ากับ Code ที่หามาได้(ข้างล่าง) ผลที่รันออกมาได้เท่ากับ Celebrity Found:2
-----------------------------------------------------------------------------------
package test;
public class CelebrityFinding{
// people numbered from 0 to 3;
static final int SIZE = 4;
public static void main(String[] args) {
int celeb = findCandidate();
if (checkIfCelebrity(celeb)) {
System.out.println("Celebrity found: " + celeb);
} else
System.out.println("Celebrity not found");
}
static int findCandidate() {
int celeb = 0;
for (int i = 1; i < SIZE; i++) {
// if celeb knows i, celeb can't be the candidate.
if (haveAcquaintance(celeb, i)) {
celeb = i;
}
}
return celeb;
}
static boolean checkIfCelebrity(int celeb) {
for (int i = 0; i < SIZE; i++) {
// check if the celebrity knows noone and everyone knows the
// celebrity.
if ((celeb != i)
&& (!haveAcquaintance(i, celeb) || haveAcquaintance(celeb,
i))) {
return false;
}
}
return true;
}
static boolean haveAcquaintance(int a, int b) {
// assuming valid input
int[][] input = { {0,0,1,1},{0,0,1,0},{0,0,0,0},{0,0,1,0} };
return input[a] == 1 ? true : false;
}
}
-------------------------------------------------------------------------------------------------
เลยอยากให้ช่วยอธิบายอัลกอริทึมให้เข้าใจหน่อย หรือว่า ถ้า Code หรืออัลกอริทึมผิดตรงไหนช่วยบอกหรือวิธีแก้ไขให้หน่อยนะครับ จะเป็นพระคุณอย่างสูง ขอบคุณครับ
ปล.มันคือ Binary Search ใช่หรือป่าวครับ???