花朵数是这么一个N位数,它的各个位数字的N次方之和为它的本身,比如:
1^3+5^3+3^3=153
现要求三分钟之内求解21位的水仙花数。
#include <stdio.h> #include <memory.h> #include <stdlib.h> #include <sys/time.h> #define N 21 #define NUMBER_LENGTH_MAX 30 struct number { char digits[NUMBER_LENGTH_MAX]; int length; }; struct counter { int digits[10]; int offset; }; void assign(struct number *a, int b) { a->length = 0; memset(&a->digits[0], 0, NUMBER_LENGTH_MAX); if (b == 0) a->length = 1; while(b > 0) { a->digits[a->length++] = b % 10; b /= 10; } } void copy(struct number *src, struct number *dst) { dst->length = src->length; memcpy(&dst->digits[0], &src->digits[0], NUMBER_LENGTH_MAX); } void print(struct number *a) { char *p = &(a->digits[0]); char *endp = &(a->digits[0]) + a->length; do { endp--; printf("%c", "0123456789"[(int)*endp]); }while(endp != p); } void add(struct number *a, struct number *b) { int len = (a->length > b->length) ? a->length : b->length; int i; int carry = 0; int d; for (i = 0; i < len; i++) { d = (a->digits[i] + b->digits[i] + carry); a->digits[i] = d % 10; carry = d / 10; } if (carry > 0) { a->digits[len] = carry; len++; } a->length = len; } void mul(struct number *a, int b) { int carry = 0; char *p = &(a->digits[0]); char *endp = &(a->digits[0]) + a->length; while(p != endp) { int d = carry + *p * b; *p = d % 10; carry = d / 10; p++; } if (carry > 0) { *p = carry; a->length++; } } int judge(struct counter *ctr, struct number *b, struct number *table) { static struct number t; static int i; assign(b, 0); for (i = 9; i >= ctr->offset; i--) { if (ctr->digits[i] > 0) { copy(&table[(i * (N + 1)) + ctr->digits[i]], &t); add(b, &t); } } static struct counter new_ctr; memset(&new_ctr, 0, sizeof(new_ctr)); new_ctr.offset = 0; char *p = b->digits; char *endp = b->digits + b->length; if (b->length != N) return 0; while (p != endp) { new_ctr.digits[(int)*p]++; p++; } for (i = 0; i < ctr->offset; i++) { if (new_ctr.digits[i] != 0) return 0; } for (i = ctr->offset + 1; i < 10; i++) { if (ctr->digits[i] != new_ctr.digits[i]) return 0; } return 1; } int iter(struct number *table) { struct counter ctr; ctr.offset = 9; int remain = 0; ctr.digits[9] = N; while (1){ if (remain == 0) { struct number sum; if (judge(&ctr, &sum, table)) { print(&sum);printf("\n"); } if (ctr.digits[ctr.offset] > 0) { ctr.digits[ctr.offset]--; remain++; } else { while (ctr.digits[ctr.offset] == 0) ctr.offset++; } } else { if (ctr.offset > 0) { ctr.offset--; ctr.digits[ctr.offset] = remain; remain = 0; } else { if (ctr.offset == 0 && remain == N) return 0; while (ctr.digits[ctr.offset] == 0) ctr.offset++; ctr.digits[ctr.offset]--; remain++; } } } return 0; } void init_table(struct number *table) { int i, j; for (i = 0; i < 10; i++) { assign(&table[i * (N + 1)], 0); assign(&table[i * (N + 1) + 1], i); for (j = 0; j < N - 1; j++) { mul(&table[i * (N + 1) + 1], i); } for (j = 2; j <= N; j++) { copy(&table[i * (N + 1) + j - 1], &table[i * (N + 1) + j]); add(&table[i * (N + 1) + j], &table[i * (N + 1) + 1]); } } } int main(int argc, const char *argv[]) { struct number *table = (struct number *)malloc(sizeof(struct number) * ((N + 1) * 10)); struct timeval time1, time2; gettimeofday(&time1, NULL); init_table(table); iter(table); free(table); gettimeofday(&time2, NULL); printf("time:%lu:%lu\n", time2.tv_sec - time1.tv_sec, time2.tv_usec - time1.tv_usec); return 0; }