[ create a new paste ] login | about

Link: http://codepad.org/nWli4yR6    [ raw code | output | fork ]

C, pasted on Aug 24:
/*
    立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.
*/

#include <stdio.h>
#include <stdlib.h>

#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


Create a new paste based on this one


Comments: