|
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | ||||
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 |
양수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다. 예를 들어 f(13)=6이다. f(n)=n이 되는 첫번째 양수는 1이다. 두번째 양수는 무엇인가. [GGGG] 다음에 난 기사를 보다가 살짜쿵 호기심이 생겼다. 구글이라는데 또 발끈해서 문제를 풀어볼라고 낑낑대다가 안돼는 것이었다. 점화식 어쩌고 저쩌고 식 세우다가 나의 초라한 수학적 한계를 실감하고는 컴퓨터에게 물었다. 컴퓨터는 199981이라고 나에게 알려줬으나 정답인지 확인할 길은 없다. 그거 다 헤아리고 있을 수도 없공 ㅋㅋ- 구글에 들어가려면 역시 똑똑해야 하긴 하나 보다. ㅎㅎ- 수학 잘하는 사람이 부러울 때는 정말 이럴때 말고는 ㅎㅎ-~ ^^ 아래는 풀어본 소스 코드다. 그냥 재귀로 만드니 스택 오버플로 나는거 같아서 캐쉬를 쓰도록 고쳤다가 생각해보니 그럴 필요도 없을것 같았다. 그래서 변수 하나로 대체한것이 두번째 루프다. [CPP]#include <stdio.h> #include <map> using namespace std; map<int, int> g_Cache; int gf(int n) { int k, r = 0; do { k = n % 10; if(k == 1) ++r; } while ((n /= 10) > 0); return r; } int f(int n) { map<int,int>::iterator it = g_Cache.find(n); if(it != g_Cache.end()) return it->second; int result; if(n <= 1) { result = n; } else { it = g_Cache.find(n-1); if(it != g_Cache.end()) result = it->second + gf(n); else result = f(n-1) + gf(n); } g_Cache.insert(make_pair(n, result)); return result; } int main() { int i; for(i = 2; f(i) != i; ++i) ; printf("%d\n", i); int last = 1; for(i = 2; (last += gf(i)) != i; ++i) ; printf("%d\n", i); return 0; }[/CPP] |
