A tromino is a group of three unit squares arranged in an L-shape. Consider the following tiling problem: The input is an array of unit squares where is a positive power of 2, with one forbidden square on the array. The output is a tiling of the array that satisfies the following conditions: Every unit square other than the input square is covered by a tromino. No tromino covers the input square. T(n) = 7T ( 5 + n ) 10n for n > 1 T(1) = 1 n S(n) = 2 n − 1 S(n) n m × m mCOMPUTER ALGORITHMS - HW #2 2 No two trominos overlap. No tromino extends beyond the board. Write a divide-and-conquer algorithm that solves this problem.
[ 해결 코드 ]
(미해결 ㅠ 에러가 조금 있는 것 같다ㅠㅠ)
#include<stdio.h>
#define m 128 //2^7
int arr[m][m];
int tile_num=0;
void put_tile(int x1, int y1, int x2, int y2,
int x3, int y3) {
tile_num++;
arr[x1][y1] = tile_num;
arr[x2][y2] = tile_num;
arr[x2][y2] = tile_num;
}
void calculate_tiling(int n, int x, int y) {
int a=0, b=0;
// 2*2 만 남았을 때 빈 칸 빼고 다 타일 놓기
if (n == 2) {
tile_num++;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[x + i][y + i] == 0) {
arr[x + i][y + i] = tile_num;
}
}
}
return 0;
}
//빈 칸(a,b) 찾기
for (int i = x; i < x + n; i++) {
for (int j = y; j < y + n; j++) {
if (arr[i][j] != 0) {
a = i, b = j;
}
}
}
//2 1
//3 4
//빈 칸이 1사분면 (+,+)
if (a >= x + (n / 2) && b >= y + (n / 2))
put_tile(x + (n / 2) - 1, y + (n / 2),
x + (n / 2), y + (n / 2) - 1,
x + (n / 2) - 1, y + (n / 2) - 1);
//빈 칸이 2사분면 (-, +)
else if (a < x + (n / 2) && b >= y + (n / 2))
put_tile(x + (n / 2), y + (n / 2) -1,
x + (n / 2), y + (n / 2),
x + (n / 2) - 1, y + (n / 2) - 1);
//빈 칸이 3사분면 (-, -)
else if (a < x + (n / 2) && b < y + (n / 2))
put_tile(x + (n / 2), y + (n / 2) - 1,
x + (n / 2), y + (n / 2),
x + (n / 2) - 1, y + (n / 2) );
//빈 칸이 4사분면 (+, -)
else if (a >= x + (n / 2) && b < y + (n / 2))
put_tile(x + (n / 2) -1, y + (n / 2),
x + (n / 2), y + (n / 2),
x + (n / 2) - 1, y + (n / 2) - 1);
//divide and conquer
calculate_tiling(n / 2, x, y + (n / 2));
calculate_tiling(n / 2, x, y);
calculate_tiling(n / 2, x + (n / 2), y);
calculate_tiling(n / 2, x + (n / 2), y + (n / 2));
return 0;
}
int main()
{
//빈 셀
arr[0][0] = -1;
int n = 8; //128=2^7 -> 7+1=8
calculate_tiling(n, 0, 0);
//결과출력
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The Towers of Hanoi problem consists of three pegs and disks of different sizes. The object is to move the disks that are stacked, in decreasing order of their size, on one of the three pegs to a new peg using the third one as a temporary peg. The problem should be solved according to the following rules: 1 when a disk is moved, it must be placed on one of the three pegs; 2 only one disk may be moved at a time, and it must be the top disk on one of the pegs; and 3 a larger disk may never be placed on top of a smaller disk. (a) Show for your algorithm that . Here denotes the number of steps (moves), given an input of disks.)
[ 해결 코드 ]
#include<stdio.h>
int count = 0;
int hanoi(int disk_num, char from_peg, char to_peg, char tmp_peg) {
if (disk_num == 1) {
printf("Move disk#1 from %c to %c \n",from_peg, to_peg);
count++;
return;
}
hanoi(disk_num - 1, from_peg, tmp_peg, to_peg);//한 번에 한개(1)씩 옮김
printf("Move disk#%d from %c to %c \n", disk_num,from_peg, to_peg);
count++;
hanoi(disk_num - 1, tmp_peg, to_peg, from_peg);
}
int main()
{
int n = 3;
int result;
result = hanoi(n, 'A', 'C', 'B');
printf("%d", result);
return 0;
}
Write an algorithm that finds the greatest common divisor of two integers.
#include<stdio.h>
int main()
{
int a, b; //2 integers
int gcd;
printf("Enter 2 int:");
scanf_s("%d %d", &a,&b);
for (int i = 1; i <= a; i++) {
if (a % i == 0 && b % i == 0)
gcd = i;
}
printf("%d", gcd);
return 0;
}
[ Output ]
* output 예상하기, 구하기
#include <iostream>
using namespace std;
int main(void) {
int i=1, j=0, n=6;
while (j <= n / 2) {
i = 1;
while (i <= j) {
cout << j << i;
i++;
}
j++;
}
return 0;
}
[ Output ]
* O(log2n)인 지수 승 함수 (my_pow)
ive a algorithm that computes the remainder when is divided by . For simplicity, you may assume that is a power of . That is, for some positive integer .
-> 이 문제를 풀다가 pow는 double 일 때만 된다는 것을 알게되었다.
pow(x,n)%p 를 하고 싶었으나 %연산은 int일 때만 된다고 해서 my_pow를 만들기로 했다.
#include<stdio.h>
int my_pow(int x, int n){
if(n==0) //exception(n = 2^k)
return 1;
else {
int root_x = my_pow(x, n / 2);
if (n % 2 == 0) //even exp(지수)
return root_x * root_x;
else //odd exp(지수)
return root_x * root_x * x;
}
}
int main()
{
int x = 3, n = 5;
int result = my_pow(x, n); //x^^n
int p = 4;
int mod = result % p; //(x^^n) % p
printf("%d", mod);
return 0;
}
Give an algorithm for the following problem. Given a list of distinct positive integers, partition the list into two sublists, each of size , such that the difference between the sums of the integers in the two sublists is minimized. Determine the time complexity of your algorithm. You may assume that is a multiple of .)
#include<stdio.h>
#include<stdlib.h>
#define arr_size 6
int main() {
int left_sum=0, right_sum=0;
int sum = 0;
int num[arr_size] = { 5, 2, 1, 4, 6, 3 }; //array
for (int i = 0; i < arr_size; i++)
sum += num[i];
//printf("%d", sum);
right_sum = sum;
int diff = 99999999;
int diff_idx;
for (int j = 0; j < arr_size; j++) {
left_sum += num[j];
right_sum -= num[j];
if (abs(left_sum - right_sum) < diff) {
diff = abs(left_sum - right_sum);
diff_idx = j;
}
}
printf("diff_idx: %d", diff_idx);
return 0;
}
//원래는 딱 반을 나눴을 때 합의 차가 최소가 되도록 해야하는문제
//그냥 둘로 나눴을 때 합의 차가 최소가 되는 idx값 출력
