-
Notifications
You must be signed in to change notification settings - Fork 5
algorithm problem 6
Jongbin Oh edited this page Jun 8, 2013
·
1 revision
- 책에 나온 예제 입력이 무한 루프가 됩니다. 16이 안 나와요. 설명 좀 해주세요 - ["CynicJJ"]
- 자문자답 - 078은 7번째 명령으로 가라는게 아니고 7번 레지스터값의 명령으로 가라는 소리네요.
- 즉, 예제입력의 078은 7번째 명령으로 가는게 아니고 9번째 명령으로 가야함
- 왜냐하면 7번 레지스터의 값이 9이므로
- 아.. 시간 아까워.. 문제는 안 풀고 패스
#ifdef _UNIT_TEST
#include "UnitTest++.h"
#endif
#include <iostream>
class CInterpreter
{
public:
CInterpreter()
{
Reset();
};
void Reset()
{
m_CurrentIP = 0;
memset( m_Register, 0, sizeof( m_Register) );
memset( m_Ram, 0, sizeof( m_Ram) );
}
void SetRegister( int index, int value )
{
m_Register[index] = value;
}
int GetRegister( int index )
{
return m_Register[index];
}
void SetRam( int address, int value )
{
m_Ram[address] = value;
}
int GetRamData( int address )
{
return m_Ram[address];
}
void SetIP( int ip )
{
m_CurrentIP = ip;
}
int GetCurrentIP()
{
return m_CurrentIP;
}
int Execute()
{
SetIP(0);
int excutedIPCount = 0;
while( Do( m_Ram[m_CurrentIP++] ) )
{
excutedIPCount++;
}
excutedIPCount++;
return excutedIPCount;
}
bool Do( int instruction )
{
int opcode = instruction / 100;
int operand1 = ( instruction % 100 ) / 10;
int operand2 = instruction % 10;
switch( opcode )
{
case 0:
{
int secondReg = m_Register[ operand2 ];
if( secondReg )
{
int newPos = m_Register[ operand1 ];
SetIP( newPos );
}
}
break;
case 1: // halt
{
if( operand1 == 0 && operand2 == 0 )
return false;
}
break;
case 2: // set register
{
m_Register[operand1] = operand2;
}
break;
case 3: // add register
{
m_Register[operand1] += operand2;
if( m_Register[operand1] > 999 )
m_Register[operand1] -= 1000;
}
break;
case 4: // mul
{
m_Register[operand1] *= operand2;
if( m_Register[operand1] > 999 )
m_Register[operand1] -= 1000;
}
break;
case 5: // set register by other register
{
m_Register[operand1] = m_Register[operand2];
}
break;
case 6: // add register by other register value
{
m_Register[operand1] += m_Register[operand2];
if( m_Register[operand1] > 999 )
m_Register[operand1] -= 1000;
}
break;
case 7: // mul register by other register value
{
m_Register[operand1] *= m_Register[operand2];
if( m_Register[operand1] > 999 )
m_Register[operand1] -= 1000;
}
break;
case 8: // // set register by ram value
{
m_Register[operand1] = m_Ram[ m_Register[operand2] ];
}
break;
case 9: // set ram data to .. register value
{
m_Ram[ m_Register[operand2] ] = m_Register[ operand1 ];
if( m_Ram[ m_Register[operand2] ] > 999 )
m_Ram[ m_Register[operand2] ] -= 1000;
}
break;
}
return true;
}
private:
int m_CurrentIP;
int m_Register[10];
int m_Ram[1000];
};
int main()
{
#ifdef _UNIT_TEST
UnitTest::RunAllTests();
#endif
int instruction;
int caseCount;
std::string line;
getline( std::cin, line );
caseCount = atoi( line.c_str() );
// one blank
getline( std::cin, line );
CInterpreter interpreter;
for( int i = 0; i < caseCount; i++ )
{
interpreter.Reset();
getline( std::cin, line );
int address = 0;
while( !line.empty() )
{
instruction = atoi( line.c_str() );
interpreter.SetRam( address++, instruction );
getline( std::cin, line );
}
int execCount = interpreter.Execute();
if( i > 0 )
std::cout << std::endl;
std::cout << execCount << std::endl;
}
return 0;
}
#ifdef _UNIT_TEST
TEST( registerTest )
{
CInterpreter interpreter;
interpreter.SetRegister( 9, 3 );
int value = interpreter.GetRegister( 9 );
CHECK_EQUAL( 3, value );
/// register test
interpreter.Do( 239 );
value = interpreter.GetRegister( 3 );
CHECK_EQUAL( 9, value );
/// add register
interpreter.Do( 333 );
value = interpreter.GetRegister( 3 );
CHECK_EQUAL( 12, value );
/// mul register
interpreter.Do( 432 );
value = interpreter.GetRegister( 3 );
CHECK_EQUAL( 24, value );
/// set register by other register value
interpreter.SetRegister( 4, 7 );
interpreter.Do( 534 );
value = interpreter.GetRegister( 3 );
CHECK_EQUAL( 7, value );
/// add register by other register value
interpreter.SetRegister( 4, 3 );
interpreter.Do( 634 );
value = interpreter.GetRegister( 3 );
CHECK_EQUAL( 10, value );
/// mul register by other register value
interpreter.SetRegister( 4, 2 );
interpreter.Do( 734 );
value = interpreter.GetRegister( 3 );
CHECK_EQUAL( 20, value );
}
TEST( ramTest )
{
CInterpreter interpreter;
interpreter.SetRam( 10, 253 );
int value = interpreter.GetRamData( 10 );
CHECK_EQUAL( 253, value );
interpreter.SetRegister( 5, 10 );
interpreter.SetRegister( 3, 5 );
// set register by ram value
interpreter.Do( 835 );
value = interpreter.GetRegister( 3 );
CHECK_EQUAL( 253, value );
interpreter.Do( 953 );
value = interpreter.GetRamData( 253 );
CHECK_EQUAL( 10, value );
interpreter.SetIP(10);
value = interpreter.GetCurrentIP();
CHECK_EQUAL( 10, value );
// if register 5 is not zero
interpreter.Do( 35 );
value = interpreter.GetCurrentIP();
CHECK_EQUAL( 253, interpreter.GetRegister( 3 ) );
CHECK_EQUAL( 253, value );
// if register 8 is zero
interpreter.SetIP( 20 );
interpreter.SetRegister( 8, 0 );
interpreter.Do( 38 );
value = interpreter.GetCurrentIP();
CHECK_EQUAL( 20, value );
}
TEST( instructionTest )
{
CInterpreter interpreter;
int ramAddress = 0;
interpreter.SetRam( ramAddress++, 299 );
interpreter.SetRam( ramAddress++, 492 );
interpreter.SetRam( ramAddress++, 495 );
interpreter.SetRam( ramAddress++, 399 );
interpreter.SetRam( ramAddress++, 492 );
interpreter.SetRam( ramAddress++, 495 );
interpreter.SetRam( ramAddress++, 399 );
interpreter.SetRam( ramAddress++, 283 );
interpreter.SetRam( ramAddress++, 279 );
interpreter.SetRam( ramAddress++, 689 );
interpreter.SetRam( ramAddress++, 78 );
interpreter.SetRam( ramAddress++, 100 );
interpreter.SetRam( ramAddress++, 0 );
interpreter.SetRam( ramAddress++, 0 );
interpreter.SetRam( ramAddress++, 0 );
int executedCount = interpreter.Execute();
CHECK_EQUAL( 16, executedCount );
}
#endif
-
아직 안 끝났는데... 스키장 가야되서 후후...
/* @JUDGE_ID:parkpd 10033 C "test" */ /* @BEGIN_OF_SOURCE_CODE */ #include <iostream> using namespace std; #define _UNIT_TEST #ifndef _UNIT_TEST int main() { return 0; } #else #include "../../UnitTest++/src/UnitTest++.h" struct Command { Command() : cmd(0), d(0), n(0) {} Command(int cmd, int d, int n) { this->cmd = cmd; this->d = d; this->n = n; } int GetInt() const { return cmd * 100 + d * 10 + n; } void SetInt(int c) { cmd = c / 100; d = (c / 10) % 10; n = c % 10; } bool IsZero() const { return (0 == cmd) && (0 == d) && (0 == n); } int cmd; int d; int n; }; class CInterpreter { public: CInterpreter() : m_SP(0), m_Halt(false) { for (int i = 0; i < 10; ++i) { m_Register[i] = 0; } } void AddCommand(string command); void AddCommand(int cmd, int d, int n); void Run(); void DoCommand(int cmd, int d, int n); int m_Register[10]; Command m_Ram[1000]; int m_SP; bool m_Halt; }; void CInterpreter::AddCommand(string command) { const char* pCommand = command.c_str(); AddCommand(pCommand[0] - '0', pCommand[1] - '0', pCommand[2] - '0'); } void CInterpreter::AddCommand(int cmd, int d, int n) { m_Ram[m_SP++] = Command(cmd, d, n); } void CInterpreter::Run() { m_SP = 0; while(!m_Halt) { Command& cmd = m_Ram[m_SP]; DoCommand(cmd.cmd, cmd.d, cmd.n); ++m_SP; } } void RemainUnder1000(int& n) { if (1000 < n) { n = n % 1000; } } void CInterpreter::DoCommand(int cmd, int d, int n) { const int s = n; const int a = n; switch(cmd) { case 1: if (0 == d && 0 == n) { m_Halt = true; return; } case 2: // 2dn : d 레지스터를 n 으로 설정(0이상 9이하) <-- TODO m_Register[d] = n; RemainUnder1000(m_Register[d]); break; case 3: // 3dn : d 레지스터에 n 더함 m_Register[d] += n; RemainUnder1000(m_Register[d]); break; case 4: // 4dn : d 레지스터에 n 곱합 m_Register[d] *= n; RemainUnder1000(m_Register[d]); break; case 5: // 5ds : d 레지스터를 s 레지스터의 값으로 설정 m_Register[d] = m_Register[s]; break; case 6: // 6ds : s 레지스터의 값을 d 레지스터에 더함 m_Register[d] += m_Register[s]; RemainUnder1000(m_Register[d]); break; case 7: // 7ds : d 레지스터에 s 레지스터의 값을 곱함 m_Register[d] *= m_Register[s]; RemainUnder1000(m_Register[d]); break; case 8: // 8da : d 레지스터를 a 레지스터에 저장된 주소의 램에 들어있는 값으로 설정 m_Register[d] = m_Ram[m_Register[a]].GetInt(); RemainUnder1000(m_Register[d]); break; case 9: // 9ds : a 레지스터에 저장된 주소의 램에 s 레지스터의 값을 대입 m_Ram[m_Register[a]].SetInt(m_Register[s]); RemainUnder1000(m_Register[d]); break; case 0: if (m_Ram[m_Register[s]].IsZero()) { m_SP = m_Register[d]; } break; } } int main() { UnitTest::RunAllTests(); char temp; cin >> temp; return 0; } TEST(Command) { Command c; c.SetInt(123); CHECK_EQUAL(1, c.cmd); CHECK_EQUAL(2, c.d); CHECK_EQUAL(3, c.n); } TEST(CInterpreter) { CInterpreter s; s.AddCommand("123"); CHECK_EQUAL(1, s.m_SP); Command& c1 = s.m_Ram[0]; CHECK_EQUAL(1, c1.cmd); CHECK_EQUAL(2, c1.d); CHECK_EQUAL(3, c1.n); s.AddCommand("946"); CHECK_EQUAL(2, s.m_SP); Command& c2 = s.m_Ram[1]; CHECK_EQUAL(9, c2.cmd); CHECK_EQUAL(4, c2.d); CHECK_EQUAL(6, c2.n); } TEST(RemainUnder1000) { int n = 10; RemainUnder1000(n); CHECK_EQUAL(10, n); n = 1000; RemainUnder1000(n); CHECK_EQUAL(1000, n); n = 1001; RemainUnder1000(n); CHECK_EQUAL(1, n); n = 1034; RemainUnder1000(n); CHECK_EQUAL(34, n); } TEST(CInterpreter_Case1) { CInterpreter s; s.AddCommand("299"); s.AddCommand("492"); s.AddCommand("495"); s.AddCommand("399"); s.AddCommand("492"); s.AddCommand("495"); s.AddCommand("399"); s.AddCommand("283"); s.AddCommand("279"); s.AddCommand("689"); s.AddCommand("078"); s.AddCommand("100"); s.AddCommand("000"); s.AddCommand("000"); s.AddCommand("000"); s.Run(); } #endif /* @END_OF_SOURCE_CODE */