Linear Shifted Array Generator by !kKo

output_file<<((end-start)/shift)+1<<endl; // number of entries...

int j=0;
for (int i=start; i<=end; i=i+shift) // making array
{
  array[j++]=i;
}
 
//  Uncomment the following line to display the whole array.
// for (i=0;i<(end-start)/shift;i++){cout<<array[i]<<" ";} cout<<endl;
 
for (i=shift;i<=(end-start)/shift;i++) // writing to file
{
  output_file<<array[i]<<" ";
}
for (i=0;i<shift;i++) // writing to file
{
  output_file<<array[i];
  if(i<shift-1) output_file<<" ";
}
output_file<<endl;

Download Full Source Code

'geek_stuff > today' 카테고리의 다른 글

맥북을 지를까..  (3) 2006.06.21
HSBC의 OTP (One time password) device.  (3) 2006.06.01
Linear Shifted Array Generator  (0) 2006.05.31
Tistory 초대권 응모관련...  (17) 2006.05.27
Tistory.com Beta에서의 첫 글  (3) 2006.05.26
1kko.com 블로그의 변천사  (0) 2006.05.21

/*
자료구조 - 2번째 과제물.
제출 기한 : 2006. 3. 31. Friday 6:00 PM.

주어진 숫자를 radix sort algorithm (pp. 350-357) 을 이용하여 정렬하라.

예 (radix 가 10일 경우):

329        720        720        329
457        355        329        355
657        436        436        436
839  ->    457   ->   839   ->   457
436        657        355        657
720        329        457        720
355        839        657        839


Input 양식:
5                // input 개수
10329353
2340213
234091223
2342321
2341323

Output 양식:
2340213
2341323
2342321
10329353
234091223


조건:
1. 각 숫자는 최대 9자리이다.
2. Input은 C:ass2_input.txt에서 입력 받아서 C:ass2_output.txt에 출력하면 된다.
3. 제출시 파일명은 "학번_이름_반"으로 작성하세요. 여기서 반은 과제물 제출 게시판의 반입니다.(A,B,C)
  예) 200621094_홍길동_A.exe /200621094_홍길동_A.c
4. 소스 파일과 실행 파일모두 제출 하셔야 합니다.  
5. input 개수에 상관없이 작동해야 합니다. 단 integer범위를 벗어나진 않습니다.
6. c: 폴더에 실행파일이 없을 경우에도 동작해야 합니다.
7. Radix_Size에 변동 사항이 있을 경우 공지사항에 다시 올리겠습니다.
8. 공지 사항을 꼭 확인해 주세요.
*/

#include <stdlib.h>  // to use function: atoi()
#include <string.h>  // to reset buffer: memset()
#include <windows.h> // for class CTimeCouter
#include <stdio.h>  // for class CTimeCouter

#define IN_FILE "c:\\ass2_input.txt"
#define OUT_FILE "c:\\ass2_output.txt"

// global variables here
struct data{
int* list;      // input data enters here
int* temp;  // mydata.temporary data to exchange
int num_in;    // number of inputs
}mydata;

struct time{
LARGE_INTEGER   st, ed, freq ;
   double          gap ;
   BOOL            bEnable;
   char            szName[256];
   UINT            counter;
   double          fTotal_Time;
}mytime;

static void Start()
{
mytime.gap = 0.0;         // init
mytime.bEnable = FALSE;
mytime.counter = 0;
mytime.fTotal_Time = 0.0;

// system test
QueryPerformanceCounter ( &mytime.st ) ;
if ( mytime.st.QuadPart == 0 )
{
 mytime.bEnable= FALSE;
 OutputDebugString("시스템이 지원이 안됨,,, 사용할 수 없음[CTimeCounter Class]\n");
}

// start()
mytime.counter ++;
QueryPerformanceCounter ( &mytime.st ) ;
}


static void End()
{
char szMsg[64];

QueryPerformanceCounter ( &mytime.ed ) ;
QueryPerformanceFrequency ( &mytime.freq ) ;

// 소요 시간 계산
mytime.gap = ( (double) (mytime.ed.QuadPart - mytime.st.QuadPart )) / ( (double) mytime.freq.QuadPart ) ;
mytime.fTotal_Time += mytime.gap;

sprintf ( szMsg, "수행시간 %.6f초\n", mytime.gap) ;
OutputDebugString(szMsg);
}

int read(FILE * in_file)
{
char tmpr[10]="";
int i;

fscanf(in_file,"%s",&tmpr);
if (atoi(tmpr)==0) return 0; // break if input is zero
else
{
 mydata.num_in=atoi(tmpr)+1;

 mydata.list = (int*)malloc(sizeof(int)*mydata.num_in); // memory allocation as size of mydata.num_in, and link this to mydata.list
 mydata.temp = (int*)malloc(sizeof(int)*mydata.num_in); // memory allocation as size of mydata.num_in, and link this to mydata.temp

 for(i=1; i<mydata.num_in; i++)
 {
  fscanf(in_file,"%s",&tmpr);
  mydata.list[i] = atoi(tmpr);
 }
}
return 1;
}


static void sort(FILE* out_file)
{
int cnt[256], idx[256], i;

Start(); // start stopwatch

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.list[i] >> 0) & 255]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.temp[idx[(mydata.list[i] >> 0) & 255]++] = mydata.list[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.temp[i] >> 8) & (255)]++;
 for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.list[idx[(mydata.temp[i] >> 8) & 255]++] = mydata.temp[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.list[i] >> 16) & (255)]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.temp[idx[(mydata.list[i] >> 16) & 255]++] = mydata.list[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.temp[i] >> 24) & (255)]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.list[idx[(mydata.temp[i] >> 24) & 255]++] = mydata.temp[i];

End();  // stop stopwatch

fprintf(out_file,"%.10f\n", mytime.fTotal_Time);
for(i=0; i<mydata.num_in-1;i++) fprintf(out_file,"%d ", mydata.list[i]);
fprintf(out_file,"\n");
}


void main(void)
{
   FILE *in_file, *out_file;

in_file=fopen(IN_FILE,"r");
out_file=fopen(OUT_FILE,"w");

while(read(in_file)) sort(out_file);

fclose(in_file);
fclose(out_file);

free(mydata.list);
free(mydata.temp);
}

'geek_stuff > today' 카테고리의 다른 글

Tistory.com Beta에서의 첫 글  (3) 2006.05.26
1kko.com 블로그의 변천사  (0) 2006.05.21
자료구조 과제 #2  (0) 2006.05.10
자료구조 과제 #1  (0) 2006.05.10
심심해서 서버 하나를 뚫어봤다.  (0) 2006.05.08
Apple.com이 윈도우즈를 지원한다?!  (2) 2006.04.06

/*/////////////////////////////////
Data Structure Assignment #1


과제1:
Operand의 크기가 너무커서 integer type으로 처리하지 못하는 더하기 연산을 integer 덧셈처럼 처리하는 프로그램을 작성하시오.

채점에 사용될 양식
예)
input.txt

21123424543254546575767868
+4235465475678687979797

2335344365547657
-345463574687

25434665457655765879
+4547568798080980

3543454
-46576985679

..
..
..
EOF

output.txt
325243436576970808976

3655765876987908606080

654768780900897979799
..
..
..

답 생성시 음수는 숫자앞에 '-'기호를 붙이셔야 됩니다.
위의 방식으로 하겠습니다.

값 사이의 줄 공백은 input 파일에서는 처리하셔야 되고
처리가 안되어 있다면 '순서대로 2줄을 읽어들여' 처리하는 식으로 되어 있으면 됩니다.

output파일에서의 공백은 처리 안하셨어도 됩니다.
*/

#include <fstream.h> // includes iostream.h
#include <string.h>  // for strcmp()

#define IN_FILE "C:\\input.txt" // don't forget to use double '\\' instead of '\'
#define OUT_FILE "C:\\output.txt"
#define MAX_LEN 200 // up to 200 chars (w/ cr & sign, +1)
#define POSITIVE 0
#define NEGATIVE 1

void mysort(char *mychar) // clear out spaces;
{
int j=0;
char temp[MAX_LEN]=""; // clearing garbages out (will temporary store cleared *mychar values)
for (int i=0;i<=MAX_LEN+1;i++)
{
 if (mychar[i]!=' ') temp[j++]=mychar[i]; // if the character is not a blank, than save to the temp.
}
strcpy(mychar, temp); // overwrite strings with 'blank removed' ones.


int signcheck_rmv(char *mychar) // check sign and return 1 if it's negative, else 0.
{
int ret_key=0;
for (int i=0;i<=MAX_LEN+1;i++)
{
 switch(mychar[i])
 {
 case '-':
  ret_key=1;     // if it's negative turn the flag on.
 case '+':
  mychar[i]=' '; // and then change the sign symbol to a blank.
  break;
 }
}
mysort(mychar); // call sort function to remove spaces

return ret_key; // return 1 if it's negative, otherwise 0
}


void remove_zeros(char* output) // remove front zeros, ej) 001023 -> 1023
{
char temp[MAX_LEN]="";
strcpy(temp,output);

for (int i=0;(unsigned)i<strlen(temp);i++) {
 if(temp[i]>='1') break;
 else temp[i]=' ';
}
mysort(temp);

if (strcmp(temp,"")==0) strcpy(temp,"0"); // leave one '0', if output is null.
strcpy(output,temp);
}


inline int bigger(int a, int b){ if(a>b) return a; else return b; }  // return bigger integer, else return first input.


void reform(char *mychar, int len) //digit count and modify 11 as 0011 to fit for 2222
{
int j=len-strlen(mychar); //+1 is for case of increase of number over 10
if (strlen(mychar)==(unsigned)len) {} //skip if strlen(mychar) is equal to itself.
else {
 while(j--) {
  for (int i=len; i>=0; i--) //repeat as length of mychar.
  {
   if(i<=0) mychar[i]='0'; // put '0' to mychar[i] if [i] is 0.
   else mychar[i]=mychar[i-1]; //otherwise
  }
 }
}
}


void calculate_plus(char* a, char* b, char *output, int last) // calculate and saves value to *output
{
int c=0;
int inta, intb;

char temp[MAX_LEN]="";

// digit count and modify 11 as 0011 to fit for 2222
reform(a, last);
reform(b, last);
reform(temp, last);

for (int i=1;i<=last;i++)
{
 inta=a[last-i]-'0';
 intb=b[last-i]-'0'; // converts a character to an integer
 //cout<<"inta+intb:"<<inta+intb<<endl;

 temp[last-i]=(((inta+intb)%10)+c)+'0'; // perform plus calculation

 if((inta+intb)/10) // if a+b is over 10, then we need to
 {
  c=1;    // set flag to 1 which says the output is more than 10.
  if(i==last) // in case the output have more digit than input, like 999+999.
  {
   reform(temp,strlen(temp)+1); // increase one more digit
   temp[0]='1';                 // then put 1 in front.
  }
 }
 else c=0; // otherwise reset the flag
}

remove_zeros(temp);
strcpy(output,temp); // copy temp to output
}


void calculate_minus(char* a, char* b, char *output, int last) // calculate and saves value to *output
{
int inta=0, intb=0, c=0;
char temp[MAX_LEN]="";
char my_a[MAX_LEN]="";
char my_b[MAX_LEN]="";

strcpy(my_a,a);
strcpy(my_b,b);

// count digit and modify 11 as 0011 to fit for 2222
reform(temp, last);
reform(my_a, last);
reform(my_b, last);

for (int i=1;i<=last;i++)
{
 if((my_a[last-i]-'0')==0) inta=0;
 else inta=(my_a[last-i]-'0');
 if((my_b[last-i]-'0')==0) intb=0;
 else intb=(my_b[last-i]-'0'); // converts a character to an integer


 if(inta-intb-c>=0)
 {
  temp[last-i]=(((inta-intb)%10)-c)+'0'; // perform minus calculation
  c=0;
 }
 else //if(inta-intb-c<0)
 {
  temp[last-i]=(inta-intb-c+10)+'0';
  c=1;
 }
}
remove_zeros(temp);
strcpy(output, temp);
}


int calculate(char *a, char *b, char *output, int a_is_neg, int b_is_neg) //(unsigned)bigger number comes to a, return 1 when the answer is MINUS.
{
char temp[MAX_LEN]="";
int type_a=0, type_b=0, i;
int len_a=strlen(a);
int len_b=strlen(b);
int last=bigger(len_a,len_b);

int a_size=1, b_size=1;

if(len_a==len_b) // assume that we have same length, because we already reform(a)&(b)
{
 for (i=0;i<=last;i++) // compare one by one
 {
  if(a[i]>b[i]) a_size*=(i+1); // +1 to prevent result is 0,  when i==0;
  if(b[i]>a[i]) b_size*=(i+1);
 }
 //cout<<"a_size: "<<a_size<<endl<<"b_size: "<<b_size<<endl;
 if(a_size>b_size)
 {
  if(a_is_neg) {calculate_minus(a,b,output,last); return NEGATIVE;} // when a_is_big and a_is_neg, output must be NEGATIVE
  if(b_is_neg) {calculate_minus(a,b,output,last); return POSITIVE;}
  calculate_plus(a,b,output,last); return POSITIVE;
 }
 if(b_size>a_size) //switch between (a,b) is occuring here.
 {
  if(b_is_neg) {calculate_plus(b,a,output,last); return NEGATIVE;} // when b_is_big and b_is_neg, output must be NEGATIVE
  if(a_is_neg) {calculate_plus(b,a,output,last); return POSITIVE;}
  calculate_plus(a,b,output,last); return POSITIVE;
 }
 calculate_plus(a,b,output,last); return POSITIVE;
}


int LONG=1;  //define as variable because we have to change later..
int SHORT=0;
//negative=1
//positive=0

if (len_a>len_b) { type_a=LONG; type_b=SHORT; }
if (len_b>len_a) { type_b=LONG; type_a=SHORT; }
if (a_is_neg) type_a+=NEGATIVE; else type_a+=POSITIVE;
if (b_is_neg) type_b+=NEGATIVE; else type_a+=POSITIVE;

// long-  type_x=2,
// long+  type_x=1,
// short- type_x=1,
// short+ type_x=0.

// first determine two definite situation.
// long+a(1) - short-b(1) = 0 // minus_calc, return POSITIVE
// long+a(1) - short+b(0) = 1 // plus_calc, return POSITIVE
// long-a(2) - short-b(1) = 1 // plus_calc, return NEGATIVE
// long-a(2) - short+b(0) = 2 // minus_calc, return NEGATIVE
// short+a(0) - long-b(2) = -2 // switch, minus_calc, return NEGATIVE
// short+a(0) - long+b(1) = -1 // plus_calc, return POSITIVE
// short-a(1) - long-b(2) = -1 // plus_calc, return NEGATIVE
// short-a(1) - long+b(1) = 0 // switch, minus_calc, return NEGATIVE

// now arranging by output, we can see top 2 has distinctive output.

// long-a(2) - short+b(0) = 2 // minus_calc, return NEGATIVE
// short+a(0) - long-b(2) = -2 // switch, minus_calc, return NEGATIVE

// long+a(1) - short-b(1) = 0 // minus_calc, return POSITIVE
// short-a(1) - long+b(1) = 0 // switch, minus_calc, return NEGATIVE
// long+a(1) - short+b(0) = 1 // plus_calc, return POSITIVE
// long-a(2) - short-b(1) = 1 // plus_calc, return NEGATIVE
// short+a(0) - long+b(1) = -1 // plus_calc, return POSITIVE
// short-a(1) - long-b(2) = -1 // plus_calc, return NEGATIVE

// so we can write:
if ( (type_a-type_b) == 2 ) { calculate_minus(a,b,output,last); return NEGATIVE; }
else if ( (type_a-type_b) == -2 ) { calculate_minus(b,a,output,last); return NEGATIVE; }

// now we have 6 conditions left, so we change the calculation from a-b to a+b.
// then we'll have two distinctive output from them.

// long+a(1) + short-b(1) = 2 // minus_calc, return POSITIVE
// short-a(1) + long+b(1) = 0 // switch, minus_calc, return NEGATIVE

// long+a(1) + short+b(0) = 1 // plus_calc, return POSITIVE
// long-a(2) + short-b(1) = 3 // plus_calc, return NEGATIVE
// short+a(0) + long+b(1) = 1 // plus_calc, return POSITIVE
// short-a(1) + long-b(2) = 3 // plus_calc, return NEGATIVE

// so we can write:
else if ( (type_a+type_b) == 2 ) { calculate_minus(a,b,output,last); return POSITIVE; }
else if ( (type_a+type_b) == 0 ) { calculate_minus(b,a,output,last); return NEGATIVE; }

// now we have 4 conditions left, so we change the definition of long
// now change the def of long.
else{
 LONG=10;
 type_a=type_b=0; //reset type_a and type_b

 // recalculate then.
 if (len_a>len_b) { type_a=LONG; type_b=SHORT; }
 if (len_b>len_a) { type_b=LONG; type_a=SHORT; }
 if (a_is_neg) type_a+=NEGATIVE; else type_a+=POSITIVE;
 if (b_is_neg) type_b+=NEGATIVE; else type_a+=POSITIVE;

 // LONG=10
 // SHORT=0
 // NEGATIVE=1
 // POSITIVE=0
 
 // which makes
 // long-  type_x=11,
 // long+  type_x=10,
 // short- type_x=1,
 // short+ type_x=0.

 // we perform the plus calculations to determine next top two.
 // long+a(10) + short+b(0) = 10 // plus_calc, return POSITIVE
 // short+a(0) + long+b(10) = 10 // plus_calc, return POSITIVE
 
 // long-a(11) + short-b(1) = 12 // plus_calc, return NEGATIVE
 // short-a(1) + long-b(11) = 12 // plus_calc, return NEGATIVE

 // so we now can write:
 if ((type_a+type_b) == 10) { calculate_plus(a,b,output,last); return POSITIVE; }
 else { calculate_plus(a,b,output,last); return NEGATIVE; }
}

return POSITIVE; // return positive if the answer is 0 situation(a=b) like (111-111)=0
}


void main(void)
{
char a[MAX_LEN]="";
char b[MAX_LEN]="";
char output[MAX_LEN]="";  // clearing out garbages

// opening files...
ifstream input_file(IN_FILE); //open file to read
ofstream output_file(OUT_FILE); //open file to write
if(input_file.fail()) //input file check
 cerr << "Error opening "<<IN_FILE<<endl;
else if(output_file.fail()) //output file check
 cerr << "Error opening "<<OUT_FILE<<endl;
else
{
 while (! input_file.eof()) //loop starts to get lines, stops end of the file.
 {
  strcpy(output,""); // just in case if the line have odd number
  //read file by line
  input_file.getline(a, sizeof(a)); //get a line, when repeats get the next odd line
  input_file.getline(b, sizeof(b)); //get a next line, when repeats get the next even line
  if (strcmp(a,"EOF")==0 || strcmp(b,"EOF")==0) break; // break out loop when meets "EOF" string, no matter if there's more to read.
   // so, really doesn't matter either line number is on even, or odd.

  //calculation
  //remove the sign
  int is_a_neg=signcheck_rmv(a);
  int is_b_neg=signcheck_rmv(b);

  switch(calculate(a, b, output, is_a_neg, is_b_neg)) // check out whether output positive calculation or negative.
  {
  case NEGATIVE:
   reform(output,strlen(output)+1);
   output[0]='-';
  case POSITIVE:
   break;
  }

  //cout<<"a: "<<a<<endl<<"b: "<<b<<endl<<"o: "<<output<<endl;  // just for testing purpose.
  output_file<<output<<endl; // write a line to output file.
 }//end of eof checking loop
}//end of input file error checking

// closing files...
input_file.close();
output_file.close();
} //end of main(void)*/

'geek_stuff > today' 카테고리의 다른 글

1kko.com 블로그의 변천사  (0) 2006.05.21
자료구조 과제 #2  (0) 2006.05.10
자료구조 과제 #1  (0) 2006.05.10
심심해서 서버 하나를 뚫어봤다.  (0) 2006.05.08
Apple.com이 윈도우즈를 지원한다?!  (2) 2006.04.06
숫자 generator 프로그램  (0) 2006.03.27

학교에서 자료구조 수업을 듣는데, 벌써 2번째 과제가 나왔다.

첫번째 과제는 개강 첫날 수업을 듣자마자 대뜸 내주시던 교수님...

생각했던대로 쉬웠던것은 아니였다. 그리고 결과는 참담;;;


이번에는 반드시 제대로 만들리라 하고 다짐했는데,

이번과제는 radix소트를 하는 프로그램이다.

아아.. 이런... 냅다 만들어서 테스트를 하려는데 entry를 쉽게쉽게

만들기 귀찮아서 그냥 프로그램으로 해결...;

갯수를 지정할수도 있고, random인지, 거꾸로 정렬된것인지, 제대로 정렬된것인지

모두 고를수있다!

음하하하!

(일반인은 다운받아도 별 소용없는거다.)
[버그있음] 때문에 새로운 버전(checker.exe)을 다운받길 권장한다.
아~주 아주 허접한 소스 공개한다.

3/27 추가포스팅: 몇몇 버그가 있어서 소스코드와 함께 다시 올린다.
변경된 사항은 코멘트가 몇가지 추가된것, 9자리 숫자가 나와야하는데 10자리가 나오는 버그, output을 check하는 프로그램이다.


(최종버전이길 기대하면서;;)

'geek_stuff > today' 카테고리의 다른 글

심심해서 서버 하나를 뚫어봤다.  (0) 2006.05.08
Apple.com이 윈도우즈를 지원한다?!  (2) 2006.04.06
숫자 generator 프로그램  (0) 2006.03.27
뉴 개념의 PC 등장!  (0) 2006.03.10
도전 PC 100만원!  (5) 2006.02.23
옛날 컴퓨터에 대한 단상.  (3) 2006.02.13

+ Recent posts