- 論壇徽章:
- 0
|
(2)第二種方法是通過遞歸的思想
設(shè)前n-1個數(shù)為A1,A2, ... ,An-1, 則下一個數(shù)An有三種情況:
1、k=(An-1, An) > 1 (這里(An-1, An)表示這兩個數(shù)的最大公約數(shù))，則除以最大公約數(shù)后得到兩個數(shù)B1, B2，這兩個數(shù)也必定只含有因子2、3、5，所以它們在A1, A2 ... An-1中， 且必定相鄰（否則設(shè)有B1<C<B2，則k*B1 < k*C < k*B2， 則An<= k*C<k*B2=An，矛盾）。所以把所有的Ak/Ak-1組成一個列表，則使An-1*Ak/Ak-1為整數(shù)的最小的值就是An。所以這里要用一個list，把所有的Ak/Ak-1存起來并按從小到大排序
2、An-1與An互素，若An-1含有2、3、5中兩個因子，則An只有一個因子，設(shè)為k，即An=K的整數(shù)次方，顯然An=k^([以k為底的An-1的對數(shù)]+1)
3、仍是互素，但An-1只含有一個因子，則An含有兩個因子，設(shè)An=k^l*t^m， 則l從0開始遍歷，由2可以直接得到m的值，得到最小的結(jié)果
以上的2、3情況下，得到的結(jié)果需要加入到list中，1的情況不需要
得到的程序比較麻煩：
- #include <stdio.h>
- #include <memory.h>
- #include <malloc.h>
- #include <stdlib.h>
- #ifdef WIN32
- typedef __int64 int64;
- #else
- typedef long long int64;
- #endif
- int base[] = {2, 3, 5};
- #define NUM 3
- int64 get_val(int *val_ary)
- {
- int i, j;
- int64 val = 1;
- for(i=0; i < NUM; i++) {
- if(val_ary[i] > 0)
- for(j = 0; j < val_ary[i]; j++) val *= base[i];
- else
- for(j = 0; j > val_ary[i]; j--) val /= base[i];
- }
- return val;
- }
- void calc_next1(int *val_ary, int flag, int *val_next)
- {
- int i, val = (int)get_val(val_ary);
- for(i=0; i<NUM; i++) val_next[i] = 0;
- for(i=0; val > 0; i++) val /= base[flag];
- val_next[flag] = i;
- }
- void calc_next2(int *val_ary, int flag, int *val_next)
- {
- int i = (flag + 1) % 3, j = (flag + 2) % 3, k, min = 0x7fffffff;
- int tmp_val[NUM], val = (int)get_val(val_ary), max_k, val1;
- calc_next1(val_ary, i, tmp_val);
- max_k = tmp_val[i];
- for(k=0; k <= max_k; k++) {
- tmp_val[i] = val_ary[i] - k;
- tmp_val[j] = 0;
- tmp_val[flag] = val_ary[flag];
- calc_next1(tmp_val, j, tmp_val);
- tmp_val[i] = k;
- tmp_val[flag] = 0;
- while((val1 = (int)get_val(tmp_val)) < val) tmp_val[j]++;
- if(min > val1) {
- min = val1;
- memcpy(val_next, tmp_val, sizeof(tmp_val));
- }
- }
- }
- struct node
- {
- int *val_ary, *val_next;
- struct node *next;
- };
- struct node *head;
- int cmp(struct node *p_node1, struct node *p_node2)
- {
- int ary1[NUM], ary2[NUM];
- int i, min;
- int64 ret;
- for(i=0; i < NUM; i++) {
- ary1[i] = p_node1->val_next[i] + p_node2->val_ary[i];
- ary2[i] = p_node1->val_ary[i] + p_node2->val_next[i];
- }
- for(i=0; i < NUM; i++) {
- min = ary1[i] > ary2[i] ? ary2[i] : ary1[i];
- ary1[i] -= min;
- ary2[i] -= min;
- }
- ret = get_val(ary1) - get_val(ary2);
- if(ret > 0) return 1;
- else if(ret == 0) return 0;
- else return -1;
- }
- void insert(struct node *p_node)
- {
- struct node *ptr, **pre_ptr;
- for(pre_ptr = &head, ptr=head; ptr != NULL && cmp(ptr, p_node) < 0 ; pre_ptr = &ptr->next, ptr = ptr->next)
- ;
- if(ptr != NULL && cmp(ptr, p_node) == 0) {
- free(p_node->val_ary);
- free(p_node->val_next);
- free(p_node);
- }
- else{
- *pre_ptr = p_node;
- p_node->next = ptr;
- }
- }
- void free_list()
- {
- struct node *ptr, *ptr1;
- for(ptr=head; ptr!= NULL; ptr = ptr1)
- {
- ptr1 = ptr->next;
- free(ptr->val_ary);
- free(ptr->val_next);
- free(ptr);
- }
- head = NULL;
- }
- void disp()
- {
- struct node *ptr;
- for(ptr = head; ptr != NULL; ptr = ptr->next) {
- printf("val1(%d, %d, %d)\n", ptr->val_ary[0], ptr->val_ary[1], ptr->val_ary[2]);
- printf("val2(%d, %d, %d)\n", ptr->val_next[0], ptr->val_next[1], ptr->val_next[2]);
- }
- }
- void calc_next3(int *val_ary, int *val_next)
- {
- struct node *ptr;
- int i, flag = 0;
- for(ptr = head; ptr != NULL && flag == 0; ptr = ptr->next) {
- flag = 1;
- for(i=0; i < NUM; i++) {
- if( ptr->val_next[i] + val_ary[i] >= ptr->val_ary[i] ) {
- val_next[i] = ptr->val_next[i] + val_ary[i] - ptr->val_ary[i];
- }
- else {
- flag = 0;
- break;
- }
- }
- }
- }
- void calc_next(int *val_ary, int *val_next)
- {
- int mod = 0, flag1 = 0, flag2 = 0;
- int i, tmp_val[NUM];
- struct node *ptr;
- for(i = 0; i < NUM; i++) {
- if(val_ary[i] == 0) {
- mod += 1; flag1=i;
- }
- else
- flag2 = i;
- }
- switch(mod) {
- case 0:
- calc_next3(val_ary, val_next);
- return;
- case 1:
- calc_next1(val_ary, flag1, tmp_val);
- calc_next3(val_ary, val_next);
- if(get_val(val_next) > get_val(tmp_val)) {
- for(i = 0; i < NUM; i++) val_next[i] = tmp_val[i];
- break;
- }
- return;
- case 2:
- calc_next2(val_ary, flag2, tmp_val);
- calc_next3(val_ary, val_next);
- if(get_val(val_next) > get_val(tmp_val)) {
- for(i = 0; i < NUM; i++) val_next[i] = tmp_val[i];
- break;
- }
- return;
- case 3:
- val_next[0] = 1;
- val_next[1] = 0;
- val_next[2] = 0;
- break;
- }
- ptr = (struct node *)malloc(sizeof(struct node));
- ptr->val_ary = (int *)malloc(sizeof(int) * NUM);
- memcpy(ptr->val_ary, val_ary, sizeof(int) * NUM);
- ptr->val_next = (int *)malloc(sizeof(int) * NUM);
- memcpy(ptr->val_next, val_next, sizeof(int) * NUM);
- ptr->next = NULL;
- insert(ptr);
- }
- int main(int argc, char *argv[])
- {
- int i;
- int val_ary[NUM], val_next[NUM];
- for(i = 0; i < NUM; i++) val_ary[i] = 0;
- printf("1\n");
- for(i = 1; i < atoi(argv[1]); i++) {
- calc_next(val_ary, val_next);
- printf("%d\n", get_val(val_next));
- memcpy(val_ary, val_next, sizeof(val_ary));
- }
- free_list();
- }
|
|
免費注冊
發(fā)表于 2006-05-07 10:18
發(fā)表于 2006-05-07 10:26
我還以為lz說的因子是通常意義上的因子，害我想的頭發(fā)都掉了幾根