คำตอบที่ได้รับเลือกจากเจ้าของกระทู้
ความคิดเห็นที่ 2
recursive เหรอ
Basic case ก็ i >n
ทำแบบ combination 00000 00001
อันไหนแต่ละหลักบวกกันแล้ว< x ก็ backtrack
ผมหัดเขียนแต่ java ลองแปลงจาก java ละกัน
[คือไม่ได้กำหนด ชนิดการเก็บข้อมูล ผมเลยใช้ ArrayList<Integer> เก็บข้อมูลที่เรียง (ถ้าใช้ int[] อาจง่ายกว่า)
และใช้ List<ArrayList<Integer>> เก็บคำตอบที่เข้าเงื่อนไข]
public static void main(String[] args) {
int r = 4, n=2, x= 5;
List<List<Integer>> answer = new ArrayList< > ( ) ;
ArrayList<Integer> list = new ArrayList< > ( ) ;
for (int i=0; i<n; i++){
list.add(0);
}
combination(answer,r,n,list,0,0,x);
System.out.println(answer);
}
public static void combination(List answer,int r, int n,ArrayList list,int value,int index,int x){
if (index==n){
if (check(list,x,n)) answer.add(list.clone());
}else if (value<=r){
list.set(index,value);
combination(answer,r,n,list,value,index+1,x);
combination(answer,r,n,list,value+1,index,x);
}
}
public static boolean check(ArrayList list,int x, int n){
int sum = 0;
for (int i=0; i<n; i++){
sum = sum+(int)list.get(i);
}
return sum>= x;
}
ตัว recursive combination ดัดแปลงมาจาก https://www.baeldung.com/java-combinations-algorithm
Basic case ก็ i >n
ทำแบบ combination 00000 00001
อันไหนแต่ละหลักบวกกันแล้ว< x ก็ backtrack
ผมหัดเขียนแต่ java ลองแปลงจาก java ละกัน
[คือไม่ได้กำหนด ชนิดการเก็บข้อมูล ผมเลยใช้ ArrayList<Integer> เก็บข้อมูลที่เรียง (ถ้าใช้ int[] อาจง่ายกว่า)
และใช้ List<ArrayList<Integer>> เก็บคำตอบที่เข้าเงื่อนไข]
public static void main(String[] args) {
int r = 4, n=2, x= 5;
List<List<Integer>> answer = new ArrayList< > ( ) ;
ArrayList<Integer> list = new ArrayList< > ( ) ;
for (int i=0; i<n; i++){
list.add(0);
}
combination(answer,r,n,list,0,0,x);
System.out.println(answer);
}
public static void combination(List answer,int r, int n,ArrayList list,int value,int index,int x){
if (index==n){
if (check(list,x,n)) answer.add(list.clone());
}else if (value<=r){
list.set(index,value);
combination(answer,r,n,list,value,index+1,x);
combination(answer,r,n,list,value+1,index,x);
}
}
public static boolean check(ArrayList list,int x, int n){
int sum = 0;
for (int i=0; i<n; i++){
sum = sum+(int)list.get(i);
}
return sum>= x;
}
ตัว recursive combination ดัดแปลงมาจาก https://www.baeldung.com/java-combinations-algorithm
แสดงความคิดเห็น
ช่วยเขียนโค้ดภาษา c หน่อยค่ะ
มีเลขโดด 0-4 นำมาเรียง n หลัก โดยแต่ละหลักบวกกันแล้วได้มากกว่าหรือเท่ากับ x
(โดยใช้ recursive เป็นตัวหลัก)
ขอบคุณล่วงหน้าค่ะ