[project euler] 26번 문제 Programming

26번 문제는 많이 어려웠다.

1) 우선 순환소수의 마디를 어떻게 구하는건지 알기 위해, 다음 사이트를 참고해 보자.
http://gmaedu.co.kr/bbs_01/read.asp?kind=1&mode=&top=&field=&word=&page=1&webid=766

여기서 순환마디 길이를 구하기 위해 10^n -1 과 modular 계산이 필요하다.
그런데 10^n이 매우 큰 수가 될 수 있기 때문에, 배열로 표현된 큰 수 형태로 만들어서 다뤄야 한다.

2) 배열로 표현된 큰 수에 대해 %(=modular) 를 구할 수 있는 함수
3) --(=decrease) 를 할 수 있는 함수를 추가로 만들어야 한다.

/*
   Problem 26 : Reciprocal cycles 
*/

#include <iostream>
#include <cmath>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <ctime>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int modular( int n[], int max, int d, int nowi)
{
    if( max <= nowi) return (n[max])%d;

    int offset = 0;
    int e = n[nowi];

    while( true) {
        if( e >= d) break;

        e *= 10;
        offset++;
        e += n[nowi+offset];
    }

    int r = e%d;
    if ((nowi+offset+1) > max) return r;

    n[ nowi+offset+1] += r*10;
    return modular( n, max, d, nowi+offset+1);
}

void dec( int n[], int max, int d)
{
if (n[max] >=d) {
n[max] -= d;
return;
}

int i = max-1;
while (true) {
if (n[i] > 0) {
n[i]--;
n[i+1] += 10;
break;
}
i--;
}

return dec( n, max, d);
}

void set( int n[])
{
for(int i=0; i<10000; i++)
{
n[i] = 0;
}
n[0] = 1;
}

int reciprocal_cycle_length( int i) 
{
char cn[10000] = {0,};
sprintf(cn, "%d", i);
int strlength = strlen(cn);

int n[10000] = {0, };

int len = 2;
while(true) 
{
// TODO cannot handle big big powered number : use modular function!
// unsigned long long int n = ((unsigned long long int)pow(10, len)-1) % i;
set( n);
dec( n, len, 1);
//cout << "dec n[0] = " << n[0] << n[1] << endl;

int mod = modular(n, len, i, 0);
if (mod == 0) {
return len;
}
len++;
}
return len-1; 
}

int trimnumber(int n)
{
if (n%2 !=0 && n%5 != 0) return n;
if (n%2 ==0) n = n/2;
if (n%5 ==0) n = n/5;
return trimnumber(n);
}

int main(int argc, char** argv)
{
clock_t begin = clock();

// cout << "len=" << reciprocal_cycle_length( 7) << endl;
int longest = 0;
int d = 0;

for(int i=1; i<1001; i++)
{
int len = reciprocal_cycle_length( trimnumber(i));
cout << "i=" << i << ", reciprocal_cycle_len=" << len << endl;

if (len > longest) {
longest = len;
d = i;
}
}

clock_t end = clock();
cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << endl;
cout << "longest=" << longest << ", d=" << d << endl;
return 0;
}


[project euler] 25번 문제 Programming

배열을 사용한 덧셈, 곱셈 함수는 계속 만들게 되는듯.

문제를 풀다 보니 약간의 요령이 생기게 되었다.
- 실행시간을 측정해 본다. 너무 길다 싶으면.. 답을 구하기에는 부적합한 알고리즘.
- 알고리즘을 짰으면, 작은 케이스의 값으로 검증을 몇 번 해본다. 한번에 맞춘다는게 쉬운게 아니니까..

이 문제를 통해 
  • Easy Prey: Solve twenty-five of the fifty easiest problems
award를 얻게 되었다 ㅋ

/*
   Problem 25 : FIND-digit Fibonacci number
*/

#include <iostream>
#include <cmath>
#include <cstring>
#include <stdio.h>
#include <string.h>

#include <ctime>

using namespace std;

void sum( int a[], int b[], int result[], int max)
{
for(int i=0; i<max; i++)
{
int s = a[i] + b[i];

result[i] += s;

if( result[i] >= 10) {
result[i+1] += result[i]/10;
result[i] = result[i]%10; 
}
}
cout << "sum=";
for(int i=max-1; i>=0; i--)
{
cout << result[i];
}
cout << endl;
}

int digit( int arr[], int max)
{
max++;
for(int i=max-1; i>=0; i--)
{
if (arr[i] != 0){
return i;
}
}
return 0;
}

#define FIND 999 
#define BUFSIZE 1002 

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

a[0] = 1;
b[0] = 2;

clock_t begin = clock();

int nth = 2;
while( true)
{
nth++;
int mod = nth%3;
if (mod == 0){
memset( c, 0, sizeof(c));
sum(a, b, c, BUFSIZE);

int d = digit(c, FIND);
cout << "digit=" << d << endl;
if (d >= FIND) break;
} else if (mod == 1) {
memset( a, 0, sizeof(a));
sum( b, c, a, BUFSIZE);
int d = digit(a, FIND);
cout << "digit=" << d << endl;
if (d >= FIND) break;
} else {
memset( b, 0, sizeof(b));
sum( c, a, b, BUFSIZE); 
int d = digit(b, FIND);
cout << "digit=" << d << endl;
if (d >= FIND) break;
}
}
clock_t end = clock();
cout << "nth=" << nth << endl;

cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << endl;
return 0;
}


[project euler] 24번 문제 Programming

고작 이 문제를.. 며칠동안..ㅠㅠ;
아래 프로그램으로 돌린 다음 나온 결과값은, 수가 몇 번 교체될건지 이다.
즉 완전히 답이 나오는게 아니라 ^^;; 손으로 한번 더 계산해줘야 한다.
음..불만족 스럽다. 한번에 답이 나오도록 고치는 걸 TODO 로 남기자.

여튼 이 문제를 풀고 첫 뱃지 - The Journey Begins 를 얻게 되었다.


/*
  Problem 24 - Lexicographic permutations 
*/

#include <iostream>
#include <cmath>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

using namespace std;

bool find( int cur[], int idx, int val)
{
for( int i=0; i<=idx; i++)
{
if (cur[i] == val) return true;
}
return false;
}

void set_digit( int cur[], int idx)
{
/*
if( idx <= 0) {
cur[idx] = cur[idx]+1;
} else {
if (cur[idx] == -1){
cur[idx] = cur[idx-1] + 1;
} else {
cur[idx]++;
}
}
*/
cur[idx]++;
}

int getfac( int max, int cur[])
{
int maxfac = 1;
int i = 1;

while ( maxfac <= max) {
int nextfac = maxfac * i;
if (nextfac > max) {
cout << "getfac() returns. max=" << max << "  maxfac=" << maxfac << " i=" << i << " rest=" << max-maxfac << endl; 
set_digit( cur, 10-i);
//cout << "10-i=" << 10-i << " cur[10-i]=" << cur[10-i] << endl; 
return getfac( max-maxfac, cur);
}
maxfac = maxfac * i;
i++;
}

return maxfac;
}

int main(int argc, char** argv)
{
int cur[16] = {0,};
int MAX = 10000 * 100;
getfac( MAX, cur); 

cout << "cur=" << endl; 
for(int i=0; i<10; i++)
{
cout <<  cur[i] << " ";
}
cout << endl;
//cout << "cur=" << cur << endl;
return 0;
}

[영화] 이터널 선샤인 일상

10년쯤 전에 개봉한 건가?
그런데 이제야 이 영화를 저번주에 극장에서 봤지..
클레멘타인의 머리 색깔이 옛스러워 옛날 영화 느낌을 더해 주었다 ㅋㅋ
비긴어게인에서의 술주정 디렉터 마크 러팔로의 젊은 시절 너드 연기도 볼 수 있었고.

은근히 어둡고 무섭게 느껴지는 장면들이 있어서
혼자 보려 한다면 내키지 않을 것 같다.

영화의 이야기 구조 때문에 한번 보기엔 아까운 영화다.
조엘과 클레멘타인도 잘 어울리고.
칙칙하지만 나이스한, 무모할 정도로 발랄함의 어울림!

마션(책과 영화) 마음가는대로 읽기

책 정말 재밌다.

현실적인 우주 이야기를 좋아하는 사람들은(ex : 그래비티에 열광하는 사람들) 취향 저격이다.

어느 정도로 재밌냐면..
다른 책을 살 목적으로 서점에 갔다가 잠깐 서서 마션의 첫 열 장을 읽는다.
그리고 그걸 손에 쥔 채로 원래 사려던 서가에 가서 책을 고른다.
그리고 마션을 망설임 없이 함께 계산한다. ^^;;

첫장의 흡입력이 대단하고(책의 첫 문장이 아무래도 jot 됐다 임) 그 재미가 책의 끝까지 이어진다.
화성을 상상할 수 있게 해주고, 불가능을 가능으로 만들기 위한 과학적인 노력을 보는 것도 재밌고
화자가 암울하거나 그런 게 없고 시종일관 유쾌하게 써놨다.

워낙 책이 재밌어서, 영화는 책에 비해 좀 덜하다.

책에서 상상했던 걸 직접 본다는 재미가 있긴 한데 상상했던 것 만큼 SF 요소들이 멋지게 표현되지는 않았다.
인터스텔라의 웜홀/블랙홀이나, 그래비티의 우주에서 작업하는 씬은 경이로울 정도인데...
마션에서는 그런 우주의 시각적 충격은 그다지 없었던 것 같다. 

책은 텍스트로 느끼는 시시콜콜한 과학적인 재미가 대단한데, 
영화에서는 짧게 화면으로 보여주거나 축소된 편이라, 충분히 느끼지 못한 채 지나가서 아쉬웠다.
그래도 그래비티와 인터스텔라 같은 영화를 좋아하기에 재미나게는 봤음.

아무튼 영화 마션은 영화비가 아깝지 않다. 그러나 둘 중 하나만 보겠다면 책이 낫다.





1 2 3 4 5 6 7 8 9 10 다음