zzun.net zzun's blog since 2001

http://acm.uva.es/p/v1/143.html

/**
Orchard Trees
zzun
hello82@unitel.co.kr
http://zzun.net
**/

#include <iostream.h>
#include <fstream.h>

ifstream fin;

void swap(float& a, float& b)
{
       float temp = a; a = b; b = temp;
}

bool read_input(float* x, float* y)
{
       bool rtn = false;
       for (int i=0; i<3; i++)
       {
               fin >> x[i] >> y[i];
               if ( x[i] > 0 || y[i] > 0 )
                       rtn = true;
       }

       return rtn;
}

int main()
{
       fin.open("test.in");
       float* x = new float[3];
       float* y = new float[3];
       int cur_y, count, tx1, tx2;
       float a1, a2, cur_x1, cur_x2;
       bool turn;

       while ( read_input(x, y) )
       {
               if ( y[1] < y[0] && y[1] <= y[2] )
               {
                       swap( x[0], x[1] );
                       swap( y[0], y[1] );
               }
               else if ( y[2] < y[0] && y[2] < y[1] )
               {
                       swap( x[0], x[2] );
                       swap( y[0], y[2] );
               }        // for largest y

               count = 0;
               turn = false;
               cur_y = (int) y[0];

               a1 = (x[1]-x[0])/(y[1]-y[0]);
               a2 = (x[2]-x[0])/(y[2]-y[0]);

               if ( a1 > a2 ) // which is on left side
               {
                       swap( x[1], x[2] );
                       swap( y[1], y[2] );
                       swap( a1, a2 );
               }

               cur_x1 = x[0] + a1*((float)cur_y - y[0]);
               cur_x2 = x[0] + a2*((float)cur_y - y[0]);

               while ( 1 )
               {                        
                       cur_y++;

                       if ( !turn && cur_y > y[1] && cur_y <= y[2] ) // find turning point
                       {
                               a1 = (x[2]-x[1])/(y[2]-y[1]);
                               cur_x1 = x[1] + a1*((float)cur_y - y[1]);
                               cur_x2 += a2;
                               turn = true;
                       }
                       else if ( !turn && cur_y > y[2] && cur_y <= y[1] )
                       {
                               a2 = (x[1]-x[2])/(y[1]-y[2]);
                               cur_x2 = x[2] + a2*((float)cur_y - y[2]);
                               cur_x1 += a1;
                               turn = true;
                       }
                       else
                       {
                               cur_x1 += a1;
                               cur_x2 += a2;
                       }

                       if ( (cur_y<=y[1] || cur_y<=y[2]) && cur_y<100 )
                       {
                               tx1 = ( cur_x1-(int)cur_x1 == 0 ) ? (int)cur_x1 : (int)cur_x1+1;
                               tx1 = ( tx1 == 0 ) ? 1 : tx1;
                               tx2 = ( (int)cur_x2 == 100 ) ? 99 : (int)cur_x2; // no point at 0&100
                               count += tx2 - tx1 + 1;
                       }
                       else
                               break;
               }
               
               cout << count << endl;
       }

       fin.close();
}

[info]
http://acm.uva.es/p/v1/108.html
내림피아드 프로젝트의 첫번째 문제
O(N^3) 알고리즘

[test.in]
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

[n01_zzun.cpp]
/**

Max-Sum Subrectangle Search

zzun
http://zzun.net
hello82@unitel.co.kr

**/

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>

int array_size;
char** num_array;

bool read_input(char* filename)
{
       ifstream fin;
       int buf;

       fin.open( filename );

       fin >> array_size;        // take the array size N
       if ( array_size <= 0 )
       {
               cout << "Error : array size!" << endl;
               return false;
       }

       num_array = new char*[array_size];
       for (int i=0; i<array_size; i++)
               num_array[i] = new char[array_size];        // 2-dim array M-allocate

       for (int i=0; i<array_size; i++)
               for (int j=0; j<array_size; j++)
               {
                       fin >> buf;
                       num_array[i][j] = (char) buf;        // take the values
               }
       
       fin.close();

       return true;
}

int main()
{
       char* input_filename;
       int** sum;
       int max = 1 << 31;
       int local_max, local_max_candi, temp;

       input_filename = "test.in";        

       if ( !read_input(input_filename) )
               return -1;

       sum = new int*[array_size+1];        // 2-dim array for SUM from [0,0] to [x,y]
       for (int i=0; i<array_size+1; i++)
       {
               sum[i] = new int[array_size+1];
               sum[i]++;        // move the pointer to use the -1 index
       }
       sum++;        // move higher pointer too, so we can use sum[-1 ~ array_size][-1 ~ array_size]

       for (int i=-1; i<array_size; i++)
       {
               sum[i][-1] = 0;
               sum[-1][i] = 0;        // init
       }

       for (int i=0; i<array_size*2-1; i++)
               for (int j=0; j<=i; j++)
                       if ( i-j < array_size && j < array_size )
                               sum[j][i-j] = num_array[j][i-j] + sum[j-1][i-j] + sum[j][i-j-1] - sum[j-1][i-j-1];        // calculate sum[][], O(N^2)

       for (int i=0; i<array_size; i++)
               for (int k=0; k<=i; k++)
               {
                       local_max = 1 << 31;
                       local_max_candi = 0;
                       for (int j=0; j<array_size; j++)
                       {
                               temp = sum[i][j] - sum[i][j-1] - sum[k-1][j] + sum[k-1][j-1];
                               local_max_candi += temp;
                               if ( temp > local_max && temp > local_max_candi )
                                       local_max = local_max_candi = temp;
                               else if ( local_max_candi > local_max )
                                       local_max = local_max_candi;
                               else if ( temp > local_max_candi )
                                       local_max_candi = temp;
                       }
                       max = (local_max > max) ? local_max : max;
               }

       cout << max << endl;

       sum--;
       for (int i=0; i<array_size+1; i++)
       {
               sum[i]--;
               delete [] sum[i];
       }
       delete [] sum;        // M de-alloc

       return 0;
}

[info]
http://acm.uva.es/p/v1/108.html
내림피아드 프로젝트의 첫번째 문제
O(N^4) 알고리즘

[test.in]
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

[n01_zzun.cpp]
/**

Max-Sum Subrectangle Search

zzun
http://zzun.net
hello82@unitel.co.kr

**/

#include
#include
#include
#include

int array_size;
char** num_array;

bool read_input(char* filename)
{
       ifstream fin;
       int buf;

       fin.open( filename );

       fin >> array_size;        // take the array size N
       if ( array_size <=>               return false;
       }

       num_array = new char*[array_size];
       for (int i=0; i<array_size; i++)
               num_array[i] = new char[array_size];        // 2-dim array M-allocate

       for (int i=0; i<array_size; i++)
               for (int j=0; j<array_size; j++)
               {
                       fin >> buf;
                       num_array[i][j] = (char) buf;        // take the values
               }
       
       fin.close();

       return true;
}

int main()
{
       char* input_filename;
       int** sum;
       int max = 1 << 31;
       int temp;

       input_filename = "test.in";        

       if ( !read_input(input_filename) )
               return -1;

       sum = new int*[array_size+1];        // 2-dim array for SUM from [0,0] to [x,y]
       for (int i=0; i<array_size+1; i++)
       {
               sum[i] = new int[array_size+1];
               sum[i]++;        // move the pointer to use the -1 index
       }
       sum++;        // move higher pointer too, so we can use sum[-1 ~ array_size][-1 ~ array_size]

       for (int i=-1; i<array_size; i++)
       {
               sum[i][-1] = 0;
               sum[-1][i] = 0;        // init
       }

       for (int i=0; i<array_size*2-1; i++)
               for (int j=0; j<=i; j++)
                       if ( i-j < array_size && j < array_size )
                               sum[j][i-j] = num_array[j][i-j] + sum[j-1][i-j] + sum[j][i-j-1] - sum[j-1][i-j-1];        // calculate sum[][], O(N^2)

       for (int i=0; i<array_size; i++)
               for (int j=0; j<array_size; j++)
                       for (int k=0; k<=i; k++)
                               for (int l=0; l<=j; l++)
                               {
                                       temp = sum[i][j] - sum[i][l-1] - sum[k-1][j] + sum[k-1][l-1];        // calculate sum of subrectangle, O(N^4)
                                       if ( temp > max )
                                               max = temp;
                               }

       cout << max << endl;

       sum--;
       for (int i=0; i<array_size+1; i++)
       {
               sum[i]--;
               delete [] sum[i];
       }
       delete [] sum;        // M de-alloc

       return 0;
}

요즘에 보내기트위터에 보내기페이스북에 보내기미투데이에 보내기

'IT > 소스코드' 카테고리의 다른 글

[C++] Orchard Trees  (0)	2004/06/04
[C++] Maximum Sum (upgrade)  (2)	2004/05/18
[C++] Maximum Sum  (0)	2004/05/10
[C] AVL Tree  (0)	2003/10/16
[C] fork(), exec(), and wait()  (0)	2003/10/16
[C] Binary Search Tree  (0)	2003/10/11

프로그래밍 언어 / 2003년 1학기 / 한상영 교수님

[설명]
2차원에서의 15-puzzle을 3차원으로 확장한 개념.
임의의 퍼즐 배치를 입력으로 받아
Optimal Solution(최소move)을 구함.
Cell을 움직이거나, 움직임의 sequence를 입력받아 움직일 수 있음.

[puzzle.cpp]
#include <iostream.h>
#include <fstream.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#define WIDTH 4

short CELL[WIDTH][WIDTH][WIDTH];
short* CELL_S = &(CELL[0][0][0]);                // the 1-dimension alias of the 3-dimension array CELL
short MD[WIDTH*WIDTH*WIDTH][WIDTH*WIDTH*WIDTH];                        // save All possible MD values.
short ANS[1000] = {0};                                        // the optimal solution of minimum moving sequence
int bound;

bool read_input(char* filename)                        // at first, load input file (ex. from puzzle.in)
{
       ifstream in (filename);
       
       char buf;
       int current_cell = 0;
       int counter = 0;

       while (in.get(buf))
       {
               if (buf>='0' && buf<='9')
               {
                       current_cell = current_cell*10 + (buf - '0');
               }
               else if (buf == '$')
                       current_cell = 64;
               else
               {
                       if (current_cell > 64)
                       {
                               cout << "ERROR : Wrong input file." << endl;
                               return false;
                       }
                       else if (current_cell > 0)
                       {
                               CELL_S[counter] = current_cell;                        // save it in to the array
                               counter++;
                               current_cell = 0;
                       }
               }                                
       }

       in.close();

       int inv_count = 0;                        // Check whether this problem can be solved or not

       for (int i=1; i<WIDTH*WIDTH*WIDTH; i++)
       {
               if (CELL_S[i-1]>CELL_S[i])
                       inv_count++;
       }

       if (inv_count%2 == 0)
       {
               cout << "Impossible to solve!" << endl;
               return false;
       }

       return true;
}

void set_md()                                // compute Manhattan Distance of all possible pair of cells
{
       int i_x, i_y, i_z, j_x, j_y, j_z;

   for (int i=0; i<WIDTH*WIDTH*WIDTH; i++)
       {
               i_x = i % WIDTH;
               i_z = i / (WIDTH*WIDTH);
               i_y = (i - i_z*WIDTH*WIDTH) / WIDTH;
               for (int j=0; j<WIDTH*WIDTH*WIDTH; j++)
               {
                       j_x = j % WIDTH;
                       j_z = j / (WIDTH*WIDTH);
                       j_y = (j - j_z*WIDTH*WIDTH) / WIDTH;
                       
                       MD[i][j] = abs(i_x - j_x) + abs(i_y - j_y) + abs(i_z - j_z);                // |x1-x2| + |y1-y2| + |z1-z2|
               }
       }

       return;
}

int cur_MD()                                // return current sum of MDs
{
       int md = 0;

       for (int i=0; i<WIDTH*WIDTH*WIDTH; i++)
       {
               if (CELL_S[i] == 64)
                       continue;
               md += MD[i][CELL_S[i]-1];
       }

       return md;
}

bool move_to(int dir)                // move to dir
{
       int x, y, z, idx;                                // find the empty cell
       for (idx=0; idx<WIDTH*WIDTH*WIDTH; idx++)
               if (CELL_S[idx]==64) break;
       x = idx % WIDTH;
       z = idx / (WIDTH*WIDTH);
       y = (idx - z*WIDTH*WIDTH) / WIDTH;

       switch (dir)
       {
       case 1 :                                                // move up
               if (y != 0)
               {
                       CELL[z][y][x] = CELL[z][y-1][x];
                       CELL[z][y-1][x] = 64;
               }
               else
                       return false;                        // impossible to move
               break;

       case 2 :                                                // move down
               if (y != 3)
               {
                       CELL[z][y][x] = CELL[z][y+1][x];
                       CELL[z][y+1][x] = 64;
               }
               else                        
                       return false;
               break;
       
       case 3 :                                                // move left
               if (x != 0)
               {
                       CELL[z][y][x] = CELL[z][y][x-1];
                       CELL[z][y][x-1] = 64;
               }
               else
           return false;
               break;
       
       case 4 :                                                // move right
               if (x != 3)
               {
                       CELL[z][y][x] = CELL[z][y][x+1];
                       CELL[z][y][x+1] = 64;                        
               }
               else
           return false;
               break;

       case 5 :                                                // move forward
               if (z != 0)
               {
                       CELL[z][y][x] = CELL[z-1][y][x];
                       CELL[z-1][y][x] = 64;
               }
               else
           return false;        
               break;

       case 6 :                                                // move backward
               if (z != 3)
               {
                       CELL[z][y][x] = CELL[z+1][y][x];
                       CELL[z+1][y][x] = 64;                        
               }
               else
                       return false;
               break;
       
       default :
               return false;
       }

       return true;                                        // success to move
}

bool IDA(int depth, short prev)                // searching algorithm
{
       depth++;
       short opp;

       for (int i=1; i<=6; i++)
       {
               opp = (i%2 == 0) ? i-1 : i+1;                // the opposite side of moving direction.
               if (prev != opp && move_to(i))
               {
                       if (cur_MD()+depth<=bound)
                       {
                               if (depth == bound || IDA(depth, i))                // recursive call
                               {
                                       move_to(opp);                        // move back
                                       ANS[depth] = i;                        // save the answer
                                       return true;
                               }
                       }
                       move_to(opp);                        // move back
               }
       }

       return false;
}

void print_cur()                                        // print out the current status
{
       for (int i=0; i<WIDTH; i++)
       {
               for (int j=0; j<WIDTH; j++)
               {
                       for (int k=0; k<WIDTH; k++)
                       {
                               if (CELL[j][i][k] == 64)
                                       printf("  $");
                               else
                   printf("%3d", CELL[j][i][k]);
                       }
                       printf(" | ");
               }
               printf("\n");
       }
       return;
}

void search()                                                // find the optimal solution
{
       bound = cur_MD();                                // lower bound of moves in optimal solution

       if (bound != 0)
       {
               cout << "Lower Bound = " << bound << endl << "Now Searching..." << endl;

               cout << "Trying " << bound << endl;

       while(!IDA(0, -1))                        // searching start
               {
                       bound += 2;                                // if the solution wasn't found, try with bound+2 as the lower bound
                       cout << "Trying " << bound << endl;
               }

               cout << "Success!" << endl;
       }

       return;
}

int main(int argc, char* argv[])
{
       char *input_file, *output_file;//, *cmd;

       /*if (argc != 2)                                                // check the arguments
       {
               printf("ERROR : Please enter the input file name as an argument.\n");
               return 1;
       }*/

       input_file = "puzzle.in";//argv[1];

       if (!read_input(input_file))                // read the input file and save it into the array
               return 1;

       char cmd[20];
       //cmd = new char[20];

       set_md();                                                        // set the MD values

       print_cur();

       printf("$>");
       cin.getline(cmd, sizeof(cmd));                                // ready to accept a command

       while (strcmp("quit", cmd))
       {
               if (strlen(cmd)==1 && cmd[0] >= '1' && cmd[0] <= '6')                        // moving command
               {
                       if(!move_to((int)(cmd[0] - '0')))
                               cout << "Illegal Move!" << endl;                        // fail to move
                       else
                               print_cur();                                                                // success to move
               }
               else if (!strncmp("in ", cmd, 3))                        // read a sequence from a file
               {
                       char buf;
                       input_file = cmd + 3;
                       ifstream in(input_file);
                       cout << "Moving... : ";
                       while(in.get(buf))
                       {
                               if (buf >= '1' && buf <= '6')
                               {
                                       cout << buf;
                                       if(!move_to((int)(buf - '0')))
                                       {
                                               cout << " Illegal Move!" << endl;
                                               goto exit;
                                       }
                               }
                       }

                       exit :
                       in.close();
                       cout << endl;
                       print_cur();
               }
               else if (!strncmp("out ", cmd, 4))                        // solve the puzzle, and put out the optimal sequence of moves
               {
                       output_file = cmd + 4;
           search();
                       cout << "Optimal solution : " << bound << " moves." << endl;
                       ofstream out(output_file);
                       for (int i=1; ANS[i] != 0; i++)                        // ANS re-initialization for next solving
                       {
                               out << ANS[i];
                               ANS[i] = 0;
                               if (i%10 == 0)
                                       out << endl;
                       }
                       out.close();

                       print_cur();
               }
               else
                       printf("Wrong Command.\n");

               printf("$>");
               cin.getline(cmd, sizeof(cmd));
       }

       return 0;
}

컴퓨터 구조 / 2003년 1학기 / 김지홍 교수님

Booth's Algorithm을 이용한 Low Level적인 곱셈을 시뮬레이션

/*************************************************************************
**                                                                    **
**                Assignment 3. 1번 Booth's algorithm simulator                    **
**                                                                    **
**                ca49 2001-12204 이준희                                    **
**                                                                    **
*************************************************************************/

#include <stdlib.h>
#include <string.h>
#include <iostream.h>
#include <stdio.h>
#include <math.h>

void printHex(int hex)                        // int를 16진수 형식으로 출력하는 함수
{
       if (hex < 0)
               printf("0x%X", hex);                                // 음수이면, %X로 그냥 출력
       else if (hex == 0)
               printf("0x00000000");                                // 0이면 0을 출력
       else
       {
               printf("0x");
               for (int i=7; pow(16, i) > hex; i--)              // 양수이면, 그만큼 0을 앞에 출력
                       printf("0");
               printf("%X", hex);
       }
       return;
}

void booth(int mcand, int mlier, int* p)                                // 실제 곱하기를 하는 함수
{
       long long int product;                                // 64비트 정수. hi+lo 의 역할
       int prev = 0;                                        // 이전bit. 현재는 phantom zero.
       int count = 0;
       int output;                                                // for 출력

       product = mlier;                                        // product의 초기값은 multiplier

       for (int i=1; i<33; i++)
       {
               product += ((prev - (product & 1)) * mcand) << 32;        
                            // product의 상위 32bit에 [ (이전bit - 지금bit) * multilicand ] 를 더합니다.
               prev = (int)product & 1;                        // shift 하기 전에, 이전bit에 현재bit을 저장.
               product >>= 1;                                // 오른쪽 shift
               output = (mcand*output < 0) ? (product + 1) : product;
                           // 출력값이 음수일 경우 2's complement 표현을 위해 조정.
               
               if (p[count] == i)                // 출력해야하는 번째의 iteration일 경우 출력!
               {
                       printf("%dth iteration: current_product = ", i);
                       printHex(output);
                       printf(" (%d in decimal notation)\n", output);
                       p[count] = 0;
                       count++;
               }
       }

       printf("Final product = ");                                // Final product 출력!
       printHex(output);
       printf(" (%d in decimal notation)\n", output);
}

int main(int argc, char* argv[])
{
       int a, b;
       int p[32] = {0};

       if (argc < 5)                                        // argument 개수 검사
       {
               cout << "Error : The Number of argument is illegal." << endl;
               return 1;
       }

       int count = 0;

       for (int i=1; i<argc; i+=2)
       {
               if (!strcmp(argv[i], "-a"))
                       a = atoi(argv[i+1]);
               else if (!strcmp(argv[i], "-b"))
                       b = atoi(argv[i+1]);
               else if (!strcmp(argv[i], "-p"))
               {
                       p[count] = atoi(argv[i+1]);
                       count++;                        // 몇 번째의 iteration을 출력해야하는지 저장
               }
               else
               {
                       cout << "Error : Arguments is illegal." << endl;
                       return 1;
               }
       }

       printf("A : ");
       printHex(a);
       printf("\nB : ");
       printHex(b);
       printf("\n");                                                // A, B 출력

       booth(a, b, p);
       a = b = count = 0;

       char command[50] = {0};
       char seps[]   = " \t";                        // 입력받은 커맨드를 토큰으로 자를 기준
       char *token, *next;

       printf("(Booth) ");
       fgets(command, 50, stdin);

       while (strncmp(command, "exit", 4))
       {
               token = strtok( command, seps );
               next = strtok( NULL, seps );                        // 한번에 2개의 토큰을 읽음
               while( (token != NULL) && (next != NULL) )
               {
                       if (!strcmp(token, "-a"))
                               a = atoi(next);
                       else if (!strcmp(token, "-b"))
                               b = atoi(next);
                       else if (!strcmp(token, "-p"))
                       {
                               p[count] = atoi(next);
                               count++;
                       }
                       else
                       {
                               cout << "Error : Arguments is illegal." << endl;
                               return 1;
                       }

                       token = strtok( NULL, seps );
                       next = strtok( NULL, seps );
               }

               printf("A : ");
               printHex(a);
               printf("\nB : ");
               printHex(b);
               printf("\n");                                        // A, B 출력

               booth(a, b, p);
               a = b = count = 0;

               printf("(Booth) ");
               fgets(command, 50, stdin);
       }

       return 0;
}