// Dynamic.h: interface for the Dynamic class.
//
//////////////////////////////////////////////////////////////////////

#pragma warning(disable:4786)
#if !defined(AFX_DYNAMIC_H__A4ADC6F8_316B_46FE_8C8E_DA43F48439D1__INCLUDED_)
#define AFX_DYNAMIC_H__A4ADC6F8_316B_46FE_8C8E_DA43F48439D1__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "Eistream.h"
#include "Eostream.h"
#include <stack>
#include <time.h>
#include <conio.h>
using namespace Ehlib;
typedef stack<char> stack_int;

class Dynamic 
{
 char *A;
 char *B;
 stack_int s; // 스택
 int tonum; // 랜덤해서 만들어진 숫자
 char result[255+1];
 int pushcount;
 int popcount;
 int p; // testing 에서 쓰는 카운트 변수
 int q; // testing 에서 쓰는 카운트 변수
 BOOL check;
public:
 Dynamic();
 virtual ~Dynamic();
 void Input();
 void MakeB();
 void InputB();
 void Calculation(int pushcount, int popcount, char * result);
 void testing(char * stemp);
};

#endif // !defined(AFX_DYNAMIC_H__A4ADC6F8_316B_46FE_8C8E_DA43F48439D1__INCLUDED_)



// Dynamic.cpp: implementation of the Dynamic class.
//
//////////////////////////////////////////////////////////////////////

#include "Dynamic.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
int temp[255] = {0, };
void main()

 Dynamic *app = new Dynamic();
 delete app;
}

Dynamic::Dynamic()
{
 srand( (unsigned)time( NULL ) ); // srand 쓰기
 memset(result, 0, 255);
 pushcount=0;
 popcount=0;
 p=0;
 q=0;
 check = TRUE;
 Input();
 Calculation(pushcount, popcount, result);
 if(check)
  cout << "답이 없는 문자열입니다.";
}

Dynamic::~Dynamic()
{
 delete[] A;
 delete[] B;
}

//사용자에게 문자열 A 를 입력받음.
void Dynamic::Input()
{
 char tempA[255+1]="";
 eout << "**************************************" << endl;
 eout << "문자열을 입력하세요 = ";
 ein.GetStr(tempA, 255);
 eout << "**************************************" << endl;
 eout << endl;

 //일단 넣은거
 A = new CHAR[strlen(tempA)+1];
 strcpy(A, tempA); // 받은거 문자열로

 MakeB();
}

//B 문자열 만들기
void Dynamic::MakeB()
{
 tonum = strlen(A);

 for (int i=0;i<tonum;i++)
 {
  while(1)
  {
   BOOL test = TRUE;
   int ran = rand()%strlen(A);
   temp[i] = ran;
   for(int j=0;j<i;j++)
   {
    if(temp[j] == ran)
     test = FALSE; 
   }
   if(test)
    break;
  }
 }
 InputB();
}

//B 문자열 집어넣기
void Dynamic::InputB()
{
 char tempB[255+1]="";
 for (int i=0;i<tonum;i++)
  tempB[i] = A[temp[i]];
 //일단 넣은거

 B = new CHAR[strlen(tempB)+1];
 strcpy(B, tempB);
 
 cout<< "랜덤으로 생성된 문자열 =  ";
 for(i=0;i<strlen(B);i++)
  cout << B[i];
 cout << endl;
 cout << "탐색을 시작합니다.." << endl;

 pushcount = strlen(A);
 popcount = pushcount;
 getch();
 cout << endl;
 eout << "**************************************" << endl;
}

//시작
void Dynamic::Calculation(int pushcount, int popcount, char * result)
{
 char * stemp = new CHAR[strlen(A)*2+1];
 strcpy(stemp, result);

 if(pushcount > 0)
 {
  result[(strlen(A) *2) - (pushcount + popcount)] = '1';
  Calculation(pushcount-1, popcount, result);
 }

 if(popcount > 0)
 {
  if(popcount > pushcount)
  {
   result[(strlen(A) *2) - (pushcount + popcount)] = '0';
   Calculation(pushcount, popcount-1, result);
  }
 }

 if(pushcount ==  0 && popcount == 0)
 {
  testing(stemp);
 }
 delete[] stemp;
}

void Dynamic::testing(char * stemp)
{
 char K[255] = "";
 for(int i=0;i<strlen(stemp)+1;i++)
 {
  if(stemp[i]=='1')
  {
   s.push(A[p++]);
  }
  else if (stemp[i]=='0')
  {
   K[q++] = s.top();
   s.pop();
  }
 }
 p=0;q=0;
 if(strcmp(B, K)==0)
 {
  cout << "문자열 = " << A << " 랜덤 = " << B << " 동작 = " << stemp << endl;
  check = FALSE;
 }
}



****************** 설명 **********************

동적 알고리즘 문제

- 문자열 A를 입력받는다.
- 문자열 A의 내부 문자의 순서가 랜덤한 순서로 변형된 문자열 B를 생성한다.(모든 문자가 들어 있을 필요는 없다.)

다음의 1과 2의 작업은 랜덤한 순으로 진행된다.
1. 문자열 A의 문자들을 stack에 push한다.
2. stack의 문자를 pop해 온다. (pop해온 문자를 문자열 K(i)에 보관한다.


위의 작업을 하다가 문자열 K(i)와 B가 동일한 것들을 출력한다.

 

예)
입력 문자열 A: hello
생성한 문자열 B: loleh


출력결과:
push push push pop push push pop pop pop pop
push push push push pop push pop pop pop pop

'COMPUTER TECH > C, C++' 카테고리의 다른 글

선문비트 단기반 최종시험 C++ 실기  (0) 2010.08.12
피보나치 수열 작성  (0) 2010.08.12
동적 알고리즘 코딩자료  (0) 2010.08.12
직렬화  (0) 2010.08.12
배열  (0) 2010.08.12
자료구조 프로그래밍  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요