ครับ!!! ผมเคยได้ยินประโยคแบบนี้มานักต่อนักล่ะ บางคนบอกว่าผมไม่รู้จักใช้เครื่องมือให้เกิดประโยชน์
คุณกำลังเข้าใจผิดกับคำว่า "การเลือกใช้เครื่องมือ" กับ "การฝึกทักษะการแก้ปัญหา"
ที่ผมเขียนเอง เพราะผมต้องการฝึก skill เพื่อให้เกิดความคล่องตัว เมื่อเราเจอโจทย์ปัญหาลักษณะนี้ เราจะแก้มันได้รึเปล่า ลองใช้ความคิดของเราดูสิ
skill มันส่งต่อผ่านประสบการณ์กันไม่ได้ ต่อให้มีคนพยายามเล่าประสบการณ์ทั้งชีวิตของเขาให้คุณฟัง คุณก็ทำแบบเขาไม่ได้ คุณต้องฝึก ฝึก ฝึก ลงมือทำด้วยตัวคุณเองครับ
ปัญหา
โดยทั่วไป การหาความน่าจะเป็นหรือความเป็นไปได้ของสมาชิกทั้งหมดภายในเซต S ซึ่งมีสมาชิกจำนวน n ตัว
คุณจะต้องวนลูปทั้งหมด n รอบ และลึก n ชั้น ถึงจะได้ค่าทั้งหมดออกมา เช่น
S = {'A', 'B', 'C'}
n = 3 ตัว
จำนวนความเป็นไปได้ทั้งหมดคือ 3 x 3 x 3 = 27 ค่า
การเขียนโปรแกรมแบบง่ายๆ จะได้
for (var i = 0; i < S.lenght; i++){
for (var j = 0; j < S.lenght; j++){
for (var k = 0; k < S.lenght; k++){
print(S[i] + ',' + S[j] + ',' + S[k]);
}
}
}
A,A,A
A,A,B
A,A,C
A,B,A
A,B,B
...
...
...
C,B,C
C,C,A
C,C,B
C,C,C
แล้วถ้าเขาต้องการให้คุณเขียน code ที่รองรับ S ที่มี size ขนาดใดก็ได้ คุณจะเขียนยังไง?แน่นอน loop ใช้ไม่ได้ล่ะ เพราะมัน fixed ตายตัว
แล้วอะไรที่เราเอามาใช้แทน loop ได้ แถมยังเป็นแบบ dynamic อีก
คำตอบคือ Recursive ครับ
code
function probabilityWalking(topElement, elements, index, callback){
if (index < 0) {
callback(topElement);
return;
}
for (var i=0; i < elements.length; i++) {
probabilityWalking(
(topElement ? (topElement + ',') : topElement) + elements[i],
elements,
index - 1,
callback
);
}
}
using
probabilityWalking('', ['A', 'B'], 1, function(el){
console.log(el);
});
A,A
A,B
B,A
B,B
probabilityWalking('', ['A', 'B', 'C'], 2, function(el){
console.log(el);
});
A,A,A
A,A,B
A,A,C
A,B,A
A,B,B
...
...
...
C,B,C
C,C,A
C,C,B
C,C,C
ตอนนี้ code เราสามารถหาความเป็นไปได้ทั้งหมดของ S ขนาดเท่าใดก็ได้ แล้วครับ :)การนำแนวคิดไปประยุกต์ใช้
maven dependencies
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-lang3</artifactId>
<version>3.1</version>
<type>jar</type>
</dependency>
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.10</version>
<scope>test</scope>
</dependency>
Probability.java
package com.blogspot.na5cent.learning;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import org.apache.commons.lang3.StringUtils;
/**
* @author redcrow
*/
public class Probability {
private static interface Callback {
void call(String element);
}
private final List<String> elements;
private boolean distinct = false;
private boolean unique = false;
private Integer size;
private Set<String> signatures;
private Probability(List<String> elements) {
this.elements = elements;
}
public static Probability ofElements(String... elements) {
return ofElements(Arrays.asList(elements));
}
public static Probability ofElements(List<String> elements) {
return new Probability(elements);
}
public Probability size(int size) {
this.size = size;
return this;
}
public Probability distinct() {
this.distinct = true;
return this;
}
public Probability unique() {
this.unique = true;
return this;
}
private Set<String> getSignatures() {
if (signatures == null) {
signatures = new HashSet<>();
}
return signatures;
}
private boolean contains(String str, String target) {
if (!str.isEmpty()) {
String[] els = StringUtils.split(str, ":");
for (String el : els) {
if (el.equals(target)) {
return true;
}
}
}
return false;
}
private String findSignature(String str) {
String[] els = StringUtils.split(str, ":");
Arrays.sort(els);
return StringUtils.join(els, ":");
}
private boolean has(String element) {
String signature = findSignature(element);
if (getSignatures().contains(signature)) {
return true;
}
getSignatures().add(signature);
return false;
}
private void walking(String topElement, List<String> elements, int index, Callback callback) {
if (index < 0) {
if (unique && has(topElement)) {
return;
}
callback.call(topElement);
return;
}
for (String element : elements) {
if (distinct && contains(topElement, element)) {
continue;
}
walking(
(topElement.isEmpty() ? topElement : topElement + ":") + element,
elements,
index - 1,
callback
);
}
}
public List<String> find() {
if (size == null) {
size = elements.size();
}
final List<String> results = new ArrayList<>();
walking("", elements, size - 1, new Callback() {
@Override
public void call(String element) {
results.add(element);
}
});
return results;
}
}
ลองดูวิธีการเรียกใช้และผลลัพธ์ที่ Test
ProbabilityTest.java
package com.blogspot.na5cent.learning;
import java.util.Arrays;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;
/**
* @author redcrow
*/
public class ProbabilityTest {
@Test
public void allOf2ElementsSize2() {
List<String> probs = Probability
.ofElements("A", "B")
.find();
List<String> results = Arrays.asList(
"A:A",
"A:B",
"B:A",
"B:B"
);
assertEquals(probs, results);
}
@Test
public void allOf3ElementsSize3() {
List<String> probs = Probability
.ofElements("A", "B", "C")
.find();
List<String> results = Arrays.asList(
"A:A:A",
"A:A:B",
"A:A:C",
"A:B:A",
"A:B:B",
"A:B:C",
"A:C:A",
"A:C:B",
"A:C:C",
"B:A:A",
"B:A:B",
"B:A:C",
"B:B:A",
"B:B:B",
"B:B:C",
"B:C:A",
"B:C:B",
"B:C:C",
"C:A:A",
"C:A:B",
"C:A:C",
"C:B:A",
"C:B:B",
"C:B:C",
"C:C:A",
"C:C:B",
"C:C:C"
);
assertEquals(probs, results);
}
@Test
public void distinctOf2ElementsSize2() {
List<String> probs = Probability
.ofElements("A", "B")
.distinct() //ตัด A:A กับ B:B ออก เพราะ A กับ B ซ้ำกัน 2 ตัว
.find();
List<String> results = Arrays.asList(
"A:B",
"B:A"
);
assertEquals(probs, results);
}
@Test
public void distinctOf3ElementsSize3() {
List<String> probs = Probability
.ofElements("A", "B", "C")
.distinct()
.find();
List<String> results = Arrays.asList(
"A:B:C",
"A:C:B",
"B:A:C",
"B:C:A",
"C:A:B",
"C:B:A"
);
assertEquals(probs, results);
}
@Test
public void distinctOf4ElementsSize2() {
List<String> probs = Probability
.ofElements("A", "B", "C", "D")
.distinct()
.size(2)
.find();
List<String> results = Arrays.asList(
"A:B",
"A:C",
"A:D",
"B:A",
"B:C",
"B:D",
"C:A",
"C:B",
"C:D",
"D:A",
"D:B",
"D:C"
);
assertEquals(probs, results);
}
@Test
public void uniqueOf2ElementsSize2() {
List<String> probs = Probability
.ofElements("A", "B")
.unique()
.find();
List<String> results = Arrays.asList(
"A:A",
"A:B",
"B:B"
);
assertEquals(probs, results);
}
@Test
public void uniqueOf3ElementsSize3() {
List<String> probs = Probability
.ofElements("A", "B", "C")
.unique()
.find();
List<String> results = Arrays.asList(
"A:A:A",
"A:A:B",
"A:A:C",
"A:B:B",
"A:B:C",
"A:C:C",
"B:B:B",
"B:B:C",
"B:C:C",
"C:C:C"
);
assertEquals(probs, results);
}
@Test
public void uniqueAndDistinctOf2ElementsSize2() {
List<String> probs = Probability
.ofElements("A", "B")
.distinct() //ตัด A:A กับ B:B ออก เพราะ A กับ B ซ้ำกัน 2 ตัว
.unique() //A:B กับ B:A ถือเป็นตัวเดียวกัน แค่สลับตำแหน่ง
.find();
List<String> results = Arrays.asList(
"A:B"
);
assertEquals(probs, results);
}
@Test
public void uniqueAndDistinctOf3ElementsSize3() {
List<String> probs = Probability
.ofElements("A", "B", "C")
.distinct()
.unique()
.find();
List<String> results = Arrays.asList(
"A:B:C"
);
assertEquals(probs, results);
}
@Test
public void uniqueAndDistinctOf3ElementsSize2() {
List<String> probs = Probability
.ofElements("A", "B", "C")
.distinct()
.unique()
.size(2)
.find();
List<String> results = Arrays.asList(
"A:B",
"A:C",
"B:C"
);
assertEquals(probs, results);
}
@Test
public void uniqueAndDistinctOf4ElementsSize2() {
List<String> probs = Probability
.ofElements("A", "B", "C", "D")
.distinct()
.unique()
.size(2)
.find();
List<String> results = Arrays.asList(
"A:B",
"A:C",
"A:D",
"B:C",
"B:D",
"C:D"
);
assertEquals(probs, results);
}
@Test
public void uniqueAndDistinctOf4ElementsSize3() {
List<String> probs = Probability
.ofElements("A", "B", "C", "D")
.distinct()
.unique()
.size(3)
.find();
List<String> results = Arrays.asList(
"A:B:C",
"A:B:D",
"A:C:D",
"B:C:D"
);
assertEquals(probs, results);
}
}
code นี้เป็นส่วนนึงของโจทย์ที่ผมกำลังแก้อยู่ครับ โจทย์มีอยู่ว่า
ให้เขียนโปรแกรมเพื่อหาสมการทั้งหมดที่เป็นไปได้ โดยให้เรา
1. ใส่คำตอบที่อยากจะได้ลงไป
2. ใส่ตัวเลขอะไรก็ได้ กี่ตัวก็ได้ลงไป (ในที่นี้คือ S)
3. ใส่ operators + หรือ - หรือ * หรือ / ลงไปกี่ตัวก็ได้ ใน 4 ตัวนี้
แล้วให้โปรแกรมคืนค่าสมการที่เกิดจากการป้อน input ข้อ 1- 3 ทั้งหมดออกมาครับ
น่าสนุกน่ะ
ตอนนี้ผมเหลือเงื่อนไขวงเล็บทั้งหมดที่เป็นไปได้ ตามจำนวนสมาชิกใน S ครับ
ยังคิดไม่ออก ฮ่าๆๆๆ
ขอบคุณมากครับ กำลัง ศึกษาอยู่พอดีเลย
ตอบลบ