变态的算法题

KBTiller

1_MAIN_type.h

1. 
   
2. 
   
3. #ifndef MAIN_T_H
   
4. #define MAIN_T_H
   
5.     //NOTHING
   
6. #endif // MAIN_T_H
   
7. 
   

复制代码

1_MAIN_function.h

1. 
   
2. 
   
3. #ifndef MAIN_F_H
   
4. #define MAIN_F_H
   
5.     #include "1_MAIN_type.h"      
   
6.     #include "2_数字组合_function.h"  //zuhe_sz()及参数
   
7.     #include "5_处理结果_function.h"  //shuchu_jg()
   
8.     #include <stdlib.h>               //system()
   
9.      
   
10. #endif // MAIN_F_H
    
11. 
    

复制代码

1_MAIN.c

1. 
   
2. /*
   
3.   Name:花朵数问题
   
4.   Author: 键盘农夫
   
5.   Date: 17-05-11
   
6.   Description: 一个一般性解法，
   
7.                适用其他进制（<=10）、其他位数的花朵数求解
   
8. */
   
9. #include "1_MAIN_function.h"
   
10. #define ANY 0
    
11. int main( void )
    
12. {
    
13.     zuhe_sz( ZHUNBEI , ANY );    //进行数字组合<=>验算<=>存储结果
    
14.            //第一个实参为ZHUNBEI时,第二个实参没有用处
    
15.     shuchu_jg();                 //输出结果,释放内存   
    
16.     system("PAUSE");
    
17.     return 0;
    
18. }
    
19. #undef ANY
    
20. /*
    
21. 注：稍微修改一下输出的函数shuchu()，程序也适合10以上进制
    
22. */
    
23. 
    

复制代码

KBTiller

2_数字组合_type.h

1. 
   
2. 
   
3. #ifndef ZUHE_T_H
   
4. #define ZUHE_T_H
   
5.     #include "3_组合验算_type.h"      
   
6.     #include "0_问题.h"
   
7. #endif // ZUHE_T_H
   
8. 
   

复制代码

2_数字组合_function.h

1. 
   
2. 
   
3. #ifndef ZUHE_F_H
   
4. #define ZUHE_F_H
   
5.     #include "2_数字组合_type.h"
   
6.     #include "3_组合验算_function.h"   
   
7.     #include "4_大数运算_function.h"      
   
8.       
   
9.     extern void zuhe_sz( const int , const int );
   
10.     //zuhe_sz()的两个特殊参数
    
11.         #define ZHUNBEI   JINZHI
    
12.         #define WANCHENG  0
    
13. #endif // ZUHE_F_H
    
14. 
    

复制代码

2_数字组合.c

1. 
   
2. 
   
3. #include "2_数字组合_function.h"
   
4. //求"WEISU位数"的各种数字组合
   
5. //sz:某一数字，gs:该数字可能选择的最大个数
   
6. //sz: ZHUNBEI 进行必要准备
   
7. //sz: WANCHENG 组合完成（可以确定0的个数时）
   
8. extern void zuhe_sz( const int sz , const  int gs )
   
9. {
   
10.     static SHUZI_GESHU_t sj_gs , //实际的个数
    
11.                          gs_sx ; //个数的上限
    
12.    
    
13.     switch ( sz ) {
    
14.         case  ZHUNBEI:
    
15.                       jisuan_zhunbei( & gs_sx );   //计算准备
    
16.                       zuhe_sz ( sz - 1 , WEISHU ) ;
    
17.                       qing0( & gs_sx );            //对 gs_sx清0                     
    
18.                       break;
    
19.         default      :  //尝试某数字（sz）的各种可能的数目（i）
    
20.                       {
    
21.                           int i ;
    
22.                           for ( i =  0 ;
    
23.                                 i <= ( (gs < gs_sx[sz]) ? gs : gs_sx[sz] ) ;
    
24.                                 i ++  ){
    
25.                               sj_gs [ sz ] = i ;
    
26.                               zuhe_sz ( sz - 1 , gs - i ) ; //下一个数字
    
27.                               sj_gs [ sz ] = 0 ;
    
28.                           }
    
29.                       }                        
    
30.                       break;
    
31.         case WANCHENG:   
    
32.                       sj_gs [ sz ] = gs  ;         //0的个数  
    
33.                       jianyan( &sj_gs )  ;         //对数字组合验算
    
34.                       sj_gs [ sz ] = 0   ;            
    
35.                       break;
    
36.     }                     
    
37. }
    
38. 
    

复制代码

KBTiller

3_组合验算_type.h

1. 
   
2. 
   
3. #ifndef YANSUAN_T_H
   
4. #define YANSUAN_T_H
   
5.     #include "0_问题.h"
   
6.     #include "6_常用.h"   
   
7.     #include "4_大数运算_type.h"        
   
8.     typedef int     SHUZI_GESHU_t[JINZHI]   ;   //描述各个数字出现个数的类型
   
9.     // 0的个数，1的个数……JINZHI-1的个数     
   
10. #endif // YANSUAN_T_H
    
11. 
    

复制代码

3_组合验算_function.h

1. 
   
2. 
   
3. #ifndef YANSUAN_F_H
   
4. #define YANSUAN_F_H
   
5.     #include "3_组合验算_type.h"      
   
6.    
   
7.     #include "4_大数运算_function.h"         
   
8.     #include "5_处理结果_function.h"         
   
9.          
   
10.     extern void jisuan_zhunbei( SHUZI_GESHU_t * );
    
11.     extern void qing0  ( SHUZI_GESHU_t * )  ;
    
12.     extern void jianyan( SHUZI_GESHU_t * )  ;
    
13. #endif // YANSUAN_F_H
    
14. 
    

复制代码

3_组合验算.c

1. 
   
2. #include "3_组合验算_function.h"   
   
3. static DASHU_t sjb[JINZHI][WEISHU]; //数据表   
   
4. //////         1*0^N,2*0^N,……WEISHU*0^N
   
5. //////         1*1^N,2*1^N,……WEISHU*1^N
   
6. //////         1*2^N,2*2^N,……WEISHU*2^N
   
7. //////         ……
   
8. //////         1*9^N,2*9^N,……WEISHU*9^N   
   
9. //////================================================
   
10. //检验构成组合的各个数字的N次方之和的数字组合
    
11. //是否与原来的组合一致
    
12. extern void jianyan( SHUZI_GESHU_t * p_zhsm )
    
13. {
    
14.     DASHU_t he ;
    
15.     fuzhi ( & he , 0 ) ;  //初值为0
    
16.     int i ;
    
17.     for( i = 1; i < GESHU(sjb) ; i++){ //i=1, 0的N次幂不用加
    
18.        if ( (* p_zhsm)[i] == 0 )           //某数字不出现
    
19.            continue ;   
    
20.        jiaru( & he , sjb[i] + (( * p_zhsm )[i] - 1)  ); // 求和
    
21.     }
    
22.    
    
23.     if(  chaoguo_ws ( & he ) == SHI
    
24.       || bugou_ws   ( & he ) == SHI  )     //位数不符合
    
25.        return ;
    
26.    
    
27.     if ( xiangtong ( & he , p_zhsm ) == FOU )//和的组合与原来的组合不同
    
28.         return ;         
    
29.    
    
30.     jilu_jg( &he );
    
31. }
    
32. //求各个数字的N次方及其整数倍（1,2，……WEISHU倍）
    
33. //同时求出各个数字出现次数的上限存入 * p_zhsx
    
34. extern void jisuan_zhunbei( SHUZI_GESHU_t * p_zhsx )
    
35. {
    
36.     int hang , lie ;
    
37.    
    
38.     for ( hang = 0 ; hang < GESHU( sjb ) ; hang++ ){
    
39.         
    
40.         qiu_mi ( sjb[hang]  , hang , N  ) ;     //求i的N次幂
    
41.         
    
42.         for ( lie = 1 ; lie < GESHU( sjb[hang] ) ; lie ++  ) { //WEISHU
    
43.             cheng ( sjb[hang] + lie    , sjb[hang]   , lie + 1 ) ;
    
44.             
    
45.             if ( chaoguo_ws ( sjb[hang] + lie ) == SHI ) //结果超过WEISHU
    
46.                 break ;   
    
47.         }   
    
48.         (* p_zhsx)[hang] = lie  ;    // 某数字出现次数的上限值
    
49.     }
    
50. }
    
51. extern void qing0( SHUZI_GESHU_t * p_zhsx )
    
52. {
    
53.     int *p = * p_zhsx ;
    
54.     while ( p < * ( p_zhsx + 1 ))
    
55.         *p++ = 0 ;
    
56. }
    
57. 
    

复制代码

KBTiller

4_大数运算_type.h

1. 
   
2. 
   
3. #ifndef DASHU_T_H
   
4. #define DASHU_T_H
   
5.     #include "0_问题.h"
   
6.     #include "6_常用.h"
   
7.     #include "3_组合验算_type.h"
   
8.     typedef int DASHU_t[WEISHU] ; //大数类型
   
9.    
   
10. #endif // DASHU_T_H
    
11. 
    

复制代码

4_大数运算_function.h

1. 
   
2. 
   
3. #ifndef DASHU_F_H
   
4. #define DASHU_F_H
   
5.     #include "4_大数运算_type.h"
   
6.    
   
7.     #include <stdio.h>
   
8.     #include "3_组合验算_function.h"   
   
9.         
   
10.     extern void qiu_mi ( DASHU_t * const , const int , int  ) ;
    
11.     extern void fuzhi  ( DASHU_t * const , const int ) ;
    
12.     extern void cheng  ( DASHU_t * const , DASHU_t * const , const int );
    
13.     extern void jiaru  ( DASHU_t * const ,  DASHU_t * const );
    
14.     extern void shuchu ( DASHU_t * const );
    
15.     extern void copy_ds( DASHU_t * const , DASHU_t * const ) ;
    
16.     extern SF   xiaoyu     ( DASHU_t * const , DASHU_t * const ) ;
    
17.     extern SF   chaoguo_ws ( DASHU_t * const ) ;
    
18.     extern SF   bugou_ws   ( DASHU_t * const ) ;
    
19.     extern SF   xiangtong  (  DASHU_t * const  ,  SHUZI_GESHU_t * const ) ;
    
20. #endif // DASHU_F_H
    
21. 
    

复制代码

4_大数运算.c

1. 
   
2. 
   
3. #include "4_大数运算_function.h"
   
4. extern  void shuchu(  DASHU_t * const p_ds )
   
5. {
   
6.     int *w = *p_ds , *t = *(p_ds+1) -1;
   
7.     int i;
   
8.    
   
9.     while( t > w && *t == 0) //前面的0不输出
   
10.        t--;  
    
11.    
    
12.     for ( i = t - w ; i >= 0 ; i-- )
    
13.        printf("%d" , w[i]);
    
14.     putchar('\n');
    
15. }
    
16. extern void copy_ds ( DASHU_t * const p_zd, DASHU_t * const p_qd )
    
17. {
    
18.     int i ;
    
19.     for (i = 0 ; i < GESHU(*p_zd) ; i++ )
    
20.         (*p_zd)[i] = (*p_qd)[i] ;
    
21. }
    
22. //判断*p_he的组合是否与*p_szzh相同
    
23. SF xiangtong ( DASHU_t * const p_he ,  SHUZI_GESHU_t * const p_szzh )
    
24. {
    
25.     SHUZI_GESHU_t szgs ;
    
26.     int i ;
    
27.     qing0  ( & szgs ) ;
    
28.     for (i = 0 ; i < GESHU(*p_he) ; i++ )
    
29.         szgs[(*p_he)[i]]++;
    
30.    
    
31.     for(i=0;i<GESHU(szgs);i++)
    
32.         if(szgs[i]!=((*p_szzh)[i]))
    
33.             return FOU ;
    
34.         
    
35.     return SHI;
    
36. }
    
37. //进位
    
38. static void jinwei( DASHU_t * const p_ds)
    
39. {
    
40.     int *q = *p_ds ;
    
41.     while ( q < *( p_ds + 1) - 1 ){
    
42.         * ( q + 1 ) += * q / JINZHI ;
    
43.         * q++ %= JINZHI ;
    
44.     }   
    
45. }
    
46. //小于
    
47. extern SF xiaoyu  ( DASHU_t * const p_ds1 , DASHU_t * const p_ds2 )
    
48. {
    
49.     int i;
    
50.     for( i = GESHU(*p_ds1) - 1 ; i >= 0 ; i -- ){
    
51.         if( (*p_ds1)[i]<(*p_ds2)[i] )
    
52.             return SHI ;
    
53.         if( (*p_ds1)[i]>(*p_ds2)[i] )
    
54.             return FOU ;
    
55.     }
    
56.     return FOU ;   
    
57. }
    
58. //将*p_js累加入*p_he
    
59. extern void jiaru( DASHU_t * const p_he ,  DASHU_t * const p_js)
    
60. {
    
61.     int i;
    
62.     for(i=0;i<GESHU(*p_he);i++)
    
63.         (*p_he)[i] += (*p_js)[i];
    
64.         
    
65.     jinwei(p_he) ;
    
66. }
    
67. //判断是否超过WEISHU
    
68. extern SF chaoguo_ws ( DASHU_t * const p_ds )
    
69. {
    
70.     if( p_ds[1][-1] >= JINZHI ){
    
71.         return SHI ;
    
72.     }
    
73.     return FOU;
    
74. }
    
75. //判断是否位数不到WEISHU
    
76. extern SF bugou_ws ( DASHU_t * const p_ds )
    
77. {
    
78.     if( p_ds[1][-1] == 0 )
    
79.         return SHI ;
    
80.     return FOU;
    
81. }
    
82. //cs2*(*p_cs1)=>(*p_ji)
    
83. extern void cheng ( DASHU_t * const p_ji , DASHU_t * const p_cs1 , const int cs2)
    
84. {
    
85.    int *p = *p_ji ,*q = *p_cs1;
    
86.    while ( p < * ( p_ji + 1) )
    
87.         *p++ = *q++ * cs2 ;
    
88.    
    
89.    //进位
    
90.    jinwei( p_ji );   
    
91. }
    
92. //求i的n次幂，放在 * p_ds 中
    
93. extern void qiu_mi ( DASHU_t * const p_ds , const int i , int  n  )
    
94. {
    
95.     fuzhi ( p_ds , i ) ;
    
96.     while ( --n > 0 )
    
97.         cheng ( p_ds , p_ds , i);
    
98. }
    
99. //赋值，大于JINZHI的数也可以
    
100. extern  void fuzhi ( DASHU_t * const p_ds , const int i )
     
101. {
     
102.     int *q = *p_ds ;
     
103.     *q = i ;
     
104.     while ( q < *( p_ds + 1) - 1){
     
105.         * ( q + 1 ) = * q / JINZHI ;
     
106.         * q++ %= JINZHI ;
     
107.     }
     
108. }
     
109. 
     

复制代码

KBTiller

5_处理结果_type.h

1. 
   
2. 
   
3. #ifndef JIEGUO_T_H
   
4. #define JIEGUO_T_H
   
5. 
   
6.    
   
7.     #include "0_问题.h"
   
8.     #include "4_大数运算_type.h"
   
9.     typedef struct JD{
   
10.                       DASHU_t ds   ;  //大数
    
11.                       struct JD *xyg ;//下一个
    
12.                      } JIEDIAN_t ;      //节点类型
    
13.     typedef JIEDIAN_t *TOU_t  ;         //头类型
    
14. #endif // JIEGUO_T_H
    
15. 
    

复制代码

5_处理结果_function.h

1. 
   
2. #ifndef JIEGUO_F_H
   
3. #define JIEGUO_F_H
   
4.     #include "5_处理结果_type.h"
   
5.    
   
6.     #include "4_大数运算_function.h"      
   
7.     #include <stdio.h>
   
8.     #include <stdlib.h>
   
9.         
   
10.     extern void jilu_jg( DASHU_t * );
    
11.     extern void shuchu_jg ( void );
    
12.    
    
13. #endif // JIEGUO_F_H
    
14. 
    

复制代码

5_处理结果.c

1. 
   
2. 
   
3. #include "5_处理结果_function.h"
   
4. static TOU_t tou = NULL ;
   
5. static void jia_jd ( TOU_t ,TOU_t *);
   
6. static void shifang_nc(TOU_t);
   
7. static void shifang_nc( TOU_t p )
   
8. {
   
9.     TOU_t q  ;
   
10.     if( p == NULL )
    
11.         return ;
    
12.    
    
13.     q = p->xyg ;
    
14.     free(p);
    
15.     shifang_nc( q );
    
16. }
    
17. extern void jilu_jg( DASHU_t * p_ds )
    
18. {
    
19.     TOU_t p_jd ;
    
20.     if( (p_jd = malloc( sizeof (JIEDIAN_t )) ) == NULL ){
    
21.         shifang_nc( tou );
    
22.         puts("无法记录结果，程序退出");
    
23.         exit ( ! EXIT_SUCCESS ) ;
    
24.     }
    
25.    
    
26.     copy_ds ( & p_jd->ds  , p_ds ) ;   //复制
    
27.     jia_jd ( p_jd , & tou );           //加入链表(p_jd,tou)
    
28. }
    
29. //按照一定次序加入节点
    
30. static void jia_jd ( TOU_t  xjd, TOU_t  *p_xyg  )
    
31. {
    
32.     if( *p_xyg == NULL ||
    
33.         ( xiaoyu ( & xjd -> ds , &(*p_xyg)->ds )) == SHI ){/* 小于 */
    
34.         xjd->xyg = *p_xyg ;
    
35.         *p_xyg = xjd ;
    
36.         return ;
    
37.     }
    
38.     jia_jd ( xjd  , &(*p_xyg)->xyg ) ;
    
39. }
    
40. //输出结果，之后释放内存
    
41. extern void shuchu_jg( void )
    
42. {
    
43.     TOU_t temp = tou ;
    
44.     while ( temp != NULL ){
    
45.         shuchu(&temp->ds);
    
46.         temp = temp->xyg ;
    
47.     }   
    
48.     shifang_nc( tou );   
    
49.     tou = NULL ;
    
50. }
    
51. 
    

复制代码

KBTiller

6_常用.h

1. 
   
2. 
   
3. //我编程常用的成语和俚语
   
4. #ifndef CHANGYONG_H
   
5. #define CHANGYONG_H
   
6.     typedef enum { FOU , SHI } SF ;
   
7.    
   
8.     #define GESHU(A) ((sizeof (A)) / (sizeof (*(A))) )
   
9.    
   
10. #endif // CHANGYONG_H
    
11. 
    

复制代码

KBTiller

从蔡万钊、A.com、koolcoy (娶妻求贤)网友的发言中受到了许多启发，在此致谢！

koolcoy

好多年没看过用拼音写的程序了，怎么看怎么囧，有空了再来研究{:3_196:}

蔡万钊

回复 70# KBTiller


    我是 AMD64 的 Gentoo 系统。

koolcoy

昨晚想了一下这个问题，有这么一个优化方法：
将1^21 * 1, 1^21 * 2, 1^21 * 3 ... 1^21 * 21, 2^21 * 1, 2^21 * 2 ... 2^21 * 21, .... 9^21 * 21一共189个数保存起来。于是原问题抓换成从这189个数中选最多9个数出来，使得他们的和满足一定的条件。整个问题的解空间小于21^9 ，这个数字大概是5000亿，采用深搜，再根据位数为21这个条件剪一下枝，最终的解空间应该不会超过100亿。

这种算法的复杂度是O(N^9)，而不是O(9^N)，N为位数。