ข้อสอบ CT203 – ข้อย่อยหา prime factorization (ปี2008)

จงหา prime factorization ของตัวเลข 510510

คำตอบ 2 * 3 * 5 * 7 * 11 * 13 * 17

ข้อสอบ CT203 – ข้อย่อยเรื่อง gcd, lcm (ปี 2008)

กำหนดให้ a,b เป็นจำนวนจริงซึ่ง ห.ร.ม (gcd) ของ a,b เท่ากับ 50 และคูณร่วมน้อย (lcm) ของ a,b เท่ากับ 400 ถ้า a =250 แล้ว b จะเท่ากับเท่าไหร่

จาก gcd(a,b) x lcm(a,b) = a x b

ดังนั้น 50 x 400 = 250 x b

จะได้ b = 80

CT203 – ทดสอบเมทริกซ์ศูนย์-หนึ่งว่ามีคุณสมบัติสมมาตร (Symmetric) หรือไม่

การบ้าน จงเขียน algorithm ทดสอบว่าเมทริกซ์จัตุรัสที่รับเข้ามามีคุึณสมบัติสมมาตรหรือไม่

ไม่สนใจค่าของเมทริกซ์ในแนวทแยงมุม (สนใจ i != j ) ให้ตรวจสอบว่าค่าของเมทริกซ์ในแนว i,j เท่ากับค่าของเมทริกซ์ในแนว j, i หรือไม่ ????

boolean checkSymmetric(int[] matrix, int size){

for(int i=0; i<size; i++){

for(int j=0; j<size; j++){

if(i != j){

if(matrix[i][j] != matrix[j][i]){

return false;

}

}

}

}

return true;

}

**ข้อสังเกตุ ถ้าดูด้วยตานั้น เมทริกซ์ที่มีคุณสมบัติสมมาตรเมื่อสลับเปลี่ยน (transpose) จะได้ค่าทุกแถวและคอลัมน์เท่าเดิม

CT203 – ทดสอบเมทริกซ์ศูนย์-หนึ่งว่ามีคุณสมบัติสะท้อน (Reflexive) หรือไม่

การบ้าน จงเขียน algorithm หาว่าเมทริกซ์จัตุรัสนั้นสะท้อน Reflexive หรือไม่

จากหลักการที่ว่า ความสัมพันธ์ R เป็นการสะท้อนถ้าสมาชิกทุกตัวบนเส้นทแยงมุมหลักของเมทริกซ์นั้นเท่ากับ 1

เนื่องจากเป็นการเช็คในแนวทแยงมุมเท่านั้น ดังนั้นสามารถวนลูปเพียงชั้นเดียว (ด้านทแยงมุมมีแถวที่ i และหลักที่ i เท่ากัน ดังนั้นจึงไม่จำเป็นต้่องใช้ for loop 2 ชั้น)

boolean checkReflexive(int[][] matrix, int size){

for(int i=0; i<size; i++){

if(matrix[i][i] != 1){

return false;

}

}

return true;

}

ข้อสอบ CT203 – Bipartite Graph เรื่องกราฟ(ปี 2008)

จากรูปเป็น Bipartite Graph หรือไม่

คำตอบ ต้องทำการวาดรูปโดยนึกว่าต้องพยายามทำให้เป็น bipartite graph ก่อน (เริ่มจากจุด a แล้วลากเส้นทาง Edge ไปให้ครบทุกด้าน จะได้ดังรูปด้านล่าง)

เขียนอธิบาย กราฟนี้ G ประกอบด้วยจุดยอด V และด้าน E

G(V,E) โดยที่จุดยอด V ประกอบด้วย

V = {V1, V2}

เซตจุดยอด V1 = {a, b, d, e} และจุดยอด V2 = {f, c}

ส่วนด้าน E = {af, ac, bf, bc, ef, ec, df, dc}

จะเห็นว่าจุดยอด V1 และ จุดยอด V2 เป็นเซตต่างสมาชิกกัน ดังนั้นกราฟนี้จึงเป็น Bipartite Graph

ข้อสอบ CT203 – จากรูปมีวงจรออยเลอร์หรือไม่ ถ้ามีจงแสดง เรื่องกราฟ(ปี2008)

มีวงจรออยเลอร์ดังนี้

a-d-b-e-d-g-h-f-e-h-i-f-c-b-a

**หมายเหตุ  คำตอบมีได้หลายคำตอบ แต่ขอให้เดินผ่านเส้นทางทุกเส้นทางและกลับมาที่จุดเริ่มต้นอีกครั้ง ถึงจะมี Euler’s Circuit

CT203 – การบ้านหาผลรวมเลขคี่ n จำนวน เรื่อง algorithm (ปี 2008)

จงเขียน algorithm คำนวณหาผลรวมของเลขคี่ n จำนวน (ตัวอย่าง ถ้า n=3 ผลรวมจำนวนคี่ = 1+ 3 + 5)

void SumODD(int n){

int sum;

int limit = n * 2;

for(int i=1; i<limit; i=i+2){

sum = sum + i;

}

cout << “Sum = ” << sum;

}

ข้อสอบ CT203 – ข้อย่อยที่ 1 เรื่อง algorithm (ปี 2008)

จงเขียน algorithm หาค่า Mean,Max, Min

void FindMaxMin(int[] input, int sizeofarray){

int sum=0;

int max, min;

max = input[0];

min = input[0];

sum += input[0];

for(int i=1; i<=sizeofarray; i++){

if(input[i] < min){

min = input[i];

}

if(input[i] > max){

max = input[i];

}

sum += input[i];

}

cout << “Min = ” + min + “\n”;

cout << “Max = ” + max + “\n”;

cout << “Mean = ” + sum/sizeofarray + “\n”;

}

ข้อสอบ CT203 – ข้อย่อยที่ 2 เรื่อง algorithm (ปี 2008)

a1*a1+a1*a2+a1*a3+…….+a1*an

a2*a1+a2*a2+a2*a3+…….+a2*an

a3*a1+a3*a2+a3*a3+…….+a3*an

…………

an*a1+an*a2+an*a3+…….+an*an

**หมายเหตุ ในข้อสอบตัวเลขหลังตัว a จะเยื้องลงมาด้านขวาล่างของตัว a ทุกตัว

จงเขียน algorithm หาผลรวมทั้งหมดนี้แล้วหารด้วยจำนวนทั้งหมดที่นำมาบวกกัน (หาค่าเฉลี่ย Means)

void CalculateMeans(int[] a){

int sum = 0;

for(int i=1; i<=n; i++){

for(int j=1; j<=n; j++){

sum += a[i]*a[j];

}

}

cout << “Means = ” << sum/(n * n) ;

}