codepad | about

 Link:

C, pasted on Aug 24:
 ```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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 ``` ```/* 立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ. */ #include #include #define N 5 // 桁を入れ替えて得られる立方数の個数 typedef struct tree { struct tree *branch[10]; struct list *p; // 線形リストへのポインタ．葉以外では無効 } Tree; typedef struct list { struct list *next; long long int num; } List; // n^3 long long int cubicnumber(int n) { return (long long int)n * n * n; } int *count(long long int num) { int *rep; int i; rep = (int *)calloc(10, sizeof(int)); for( i = 0; num != 0; i++ ) { rep[num % 10]++; num /= 10; } return rep; } Tree *allocNodeofTree(void) { Tree *rep; int i; rep = (Tree *)malloc(sizeof(Tree)); rep->p = NULL; for( i = 0; i < 10; i++ ) { rep->branch[i] = NULL; } return rep; } List *allocNodeofList(long long int num) { List *rep; rep = (List *)malloc(sizeof(List)); rep->num = num; rep->next = NULL; return rep; } long long int add(long long int num, int *digits, Tree *root) { Tree *node = root; List *p, *head; int depth; int cnt = 0; for( depth = 0; depth < 10; depth++ ) { if( node->branch[digits[depth]] == NULL ) { node->branch[digits[depth]] = allocNodeofTree(); } node = node->branch[digits[depth]]; } if( node->p == NULL ) { node->p = allocNodeofList(num); } else { head = node->p; for( p = head; p->next != NULL; p = p->next ) { cnt++; // 手繰るノードが3つあれば，numは桁を入れ替えて得られる5つ目の立方数 if( cnt == N - 2 ) { return head->num; } } p->next = allocNodeofList(num); } return -1; } int main(void) { Tree *root; int *digits; long long int n; int i; root = allocNodeofTree(); for( i = 1;; i++ ) { long long int rep; n = cubicnumber(i); digits = count(n); rep = add(n, digits, root); if( rep == -1 ) continue; printf("%lld\n", rep); break; } return 0; } ```

Output:
 ```1 ``` ```127035954683 ```

Comments: