23.拆除脚手架 把为测试写的多余的代码删除；重新审视代码 extern SF chaoguo_W ( const DASHU * const ); 改名为 extern SF ds_chaoguo_W ( const DASHU * const );
extern SF buzu_W ( const DASHU * const ); 改名为 extern SF ds_buzu_W ( const DASHU * const );
extern void qiu_sz_gs ( int (*)[JINZHI] , const DASHU * const ) ; 改名为 extern void ds_qiu_sz_gs ( int (*)[JINZHI] , const DASHU * const ) ;
extern SF xiaoyu ( const DASHU * const , const DASHU * const ) ; 改名为 extern DX ds_bijiao ( const DASHU * const , const DASHU * const ) ; 修改了函数原型并重新进行了定义
View Code /*0_问题.h*/ #ifndef WENTI_H #define WENTI_H #define QIUJIE //求解21位问题 //#define CESHI //进行测试 #ifdef CESHI //测试 #define JINZHI 10 //十进制 #define WEISHU 3 //3位花朵数 #define N WEISHU //幂次==位数 #endif //CESHI #ifdef QIUJIE //求解 #define JINZHI 10 //十进制 #define WEISHU 21 //位数 #define N WEISHU //幂次==位数 #endif //QIUJIE #endif // WENTI_H View Code /*1_MAIN.h*/ #ifndef MAIN_H
#define MAIN_H /**************************类型定义**************************/ /**************************函数原型**************************/ #include View Code /* Name:花朵数问题 Author:键盘农夫 Date:2011,5,30 Description: */ #include "1_MAIN.h"
#include "0_问题.h" #ifdef CESHI //测试 int main( void ) { system("PAUSE"); return 0; } #endif //CESHI #ifdef QIUJIE //求解 int main( void ) { qiongju(); //求解:穷举<=>验算<=>记录结果 shuchu(); //输出 system("PAUSE"); return 0; } #endif //QIUJIEView Code /*2_穷举.h*/ #ifndef QIONGJU_H
#define QIONGJU_H /**************************类型定义**************************/ #include "3_大数.h" #include "常用.h" /**************************函数原型**************************/ extern void qiongju( void ); #include View Code /*2_穷举.c*/ #include "2_穷举.h"
#include "0_问题.h" typedef unsigned int SHUZI_GESHU[JINZHI];
//SHUZI_GESHU[d]存储出现在数字组合中数字d的个数 typedef DASHU SHUJUBIAO[JINZHI-1][WEISHU + 1];
//0*(JINZHI-1)^N 1*(JINZHI-1)^N ……WEISHU*(JINZHI-1)^N
//0*(JINZHI-2)^N 1*(JINZHI-2)^N ……WEISHU*(JINZHI-1)^N
//……
//0*(1)^N 1*(1)^N ……WEISHU*(1)^N static void xunhuan(const int , const int , DASHU (*)[WEISHU + 1] ) ;
static void jianli_sjb ( SHUJUBIAO * * ); //建立数据表
static SF wenhe( SHUZI_GESHU * const , const DASHU * const); // 判断*p_he中各数字的个数与*p_sz_gs是否吻合 static SF wenhe( SHUZI_GESHU * const p_sz_gs , const DASHU * const p_he )
{ int sz_gs_he[JINZHI] = { 0 }; //"和"中各数字的个数 if( ds_chaoguo_W(p_he) == SHI //超过W位||不足W位 || ds_buzu_W (p_he) == SHI ){ return FOU ; } ds_qiu_sz_gs( &sz_gs_he , p_he ); //求"和"中各数字的个数 if ( memcmp ( sz_gs_he , *p_sz_gs , sizeof sz_gs_he )==0 ){ return SHI ; } return FOU ;
} //建立数据表 static void jianli_sjb ( SHUJUBIAO * * p_p_sjb )
{ if( (* p_p_sjb = malloc(sizeof(SHUJUBIAO)) ) == NULL ){ exit(!EXIT_SUCCESS); } { int i , j ; for( i = 0 ; i < JINZHI - 1 ; i ++){ ds_fuzhi( *( * * p_p_sjb + i ) + 0 , 0 );//第一列为0 ds_fuzhi( *( * * p_p_sjb + i ) + 1 , 1 );//第二列先赋值为1 for( j = 0 ; j < N ; j ++ ){ //求N次幂 ds_chengyi( *( * * p_p_sjb + i ) + 1 , JINZHI - 1 - i ); } for( j = 2 ; j <= WEISHU ; j ++ ){ (*( * * p_p_sjb + i ))[j] = (*( * * p_p_sjb + i ))[j-1] ; ds_jiaru ( *( * * p_p_sjb + i ) + j , *( * * p_p_sjb + i ) + 1 ) ; } } } } extern void qiongju( void )
{ SHUJUBIAO *p_sjb = NULL ; jianli_sjb ( & p_sjb ); //建立数据表 xunhuan( WEISHU , JINZHI-1 , *p_sjb ) ; free ( p_sjb );
} static void xunhuan( const int gssx /*个数上限*/ , const int sz /*关于哪个数字*/, DASHU (*p_hang)[WEISHU + 1] /*指向一行数据*/) { static DASHU he = { { 0 } } ;//用于累加"和" static SHUZI_GESHU sz_gs ; DASHU he_ = he ; //记录累加前的值 if( sz > 0 ){ int i; for( i = 0 ; i <= gssx ; i++ ){ sz_gs[sz] = i ; //记录数字的个数 ds_jiaru ( &he , *p_hang + i ) ; xunhuan( gssx - i , sz - 1 , p_hang + 1 ); //选取下一个数字^N的倍数 he = he_ ; //恢复原来的值 } } else{ sz_gs[sz] = gssx ; //记录数字的个数 if( wenhe ( & sz_gs , &he ) == SHI ){ //验算两者是否"吻合" jilu( & he ); //<=>记录结果 } }
}View Code /*3_大数.h*/ #ifndef DASHU_H
#define DASHU_H #include "0_问题.h" //DASHU用到了WEISHU typedef enum { DAYU , //大于 DENGYU , //等于 XIAOYU //小于 } DX ; /**************************类型定义**************************/ //gw_sz[0]为个位，gw_sz[WEISHU-1]为最高位
//gw_sz[WEISHU-1]的值大于等于JINZHI表示溢出 typedef struct { int gw_sz[WEISHU] ; } DASHU ; #include "常用.h" /**************************函数原型**************************/ extern void ds_fuzhi ( DASHU * const , const int ) ; extern void ds_shuchu ( const DASHU * const ) ; extern void ds_jiaru ( DASHU * const , const DASHU * const ) ; extern void ds_chengyi( DASHU * const , const int ); extern SF ds_chaoguo_W ( const DASHU * const ); extern SF ds_buzu_W ( const DASHU * const ); extern void ds_qiu_sz_gs ( int (*)[JINZHI] , const DASHU * const ) ; extern DX ds_bijiao ( const DASHU * const , const DASHU * const ) ; #endif // DASHU_HView Code /*3_大数.c*/
#include "3_大数.h" static void ds_jinwei ( DASHU * const ); extern DX ds_bijiao ( const DASHU * const p_ds1, const DASHU * const p_ds2) { int *t1 = p_ds1-> gw_sz , * w1 = t1 + WEISHU -1 ; int *t2 = p_ds2-> gw_sz , * w2 = t2 + WEISHU -1 ; while( w1 > t1 ){ if( *w1 < *w2 ){ return XIAOYU ; } if( *w1-- > *w2-- ){ return DAYU ; } } if( *w1 < *w2 ){ return XIAOYU ; } if( *w1> *w2 ){ return DAYU ; } return DENGYU ;
} //统计*p_he中的各数字个数=> *p_sz_gs
extern void ds_qiu_sz_gs( int (*p_sz_gs)[JINZHI] , const DASHU * const p_he ) { int * t = p_he->gw_sz ; while( t < p_he->gw_sz + WEISHU ){ (*( *p_sz_gs + *t++ ))++ ;//(*p_sz_gs)[*t++] ++ ; }
} //判断是否不足WEISHU extern SF ds_buzu_W(const DASHU * const p_ds)
{ if(p_ds->gw_sz[WEISHU-1] == 0 ){ return SHI ; } return FOU ;
} //判断是否超过WEISHU extern SF ds_chaoguo_W(const DASHU * const p_ds)
{ if(p_ds->gw_sz[WEISHU-1] >=JINZHI ){ return SHI ; } return FOU ;
} //* p_ds *= cs extern void ds_chengyi( DASHU * const p_ds , const int cs )
{ int * t = p_ds->gw_sz ; while( t < p_ds->gw_sz + WEISHU ){ *t++ *=cs ; } ds_jinwei ( p_ds );
} //进位 static void ds_jinwei ( DASHU * const p_ds )
{ int * t = p_ds->gw_sz , * const w = t + WEISHU - 1 ; while( t < w ){ *( t + 1 ) += * t / JINZHI ; * t ++ %= JINZHI ; }
} // *p_he += *p_js
extern void ds_jiaru ( DASHU * const p_he , const DASHU * const p_js )
{ int *he_t = p_he->gw_sz , * const he_w = he_t + WEISHU ; const int *js_t = p_js->gw_sz ; while( he_t < he_w ){ *he_t++ += *js_t++ ; } ds_jinwei ( p_he ); } //输出 extern void ds_shuchu( const DASHU * const p_ds )
{ int * const t = p_ds->gw_sz , *w = t + WEISHU - 1 ; while( w > t && *w == 0 ){ //高位0不输出 w--; } while( w > t ){ printf( "%d" , * w -- ); } printf( "%d\n" , * t ) ;
} //在*p_ds中写入n extern void ds_fuzhi ( DASHU * const p_ds , const int n ) { p_ds->gw_sz[0] = n ; //可能有进位，同时把高位写为0 { int *t = p_ds->gw_sz , //指向 p_ds->gw_sz[0] *w = t + WEISHU - 1 ; //指向 p_ds->gw_sz[WEISHU-1] while( t < w ){ *( t + 1 ) = * t / JINZHI ; * t ++ %= JINZHI ; } }
}View Code /*4_结果.h*/ #ifndef JIEGUO_H
#define JIEGUO_H /**************************类型定义**************************/ #include "3_大数.h" typedef struct jd { DASHU hds; //花朵数 struct jd *xyg; //下一个 } JIEDIAN; #include "常用.h" /**************************函数原型**************************/ extern void jilu( DASHU * ); #include "3_大数.h" //xiaoyu() #include View Code /*4_结果.c*/
#include "4_结果.h" static JIEDIAN *tou = NULL ; //记录链表的第一个节点 extern void shuchu(void)
{ while( tou != NULL ){ JIEDIAN *p_xyg = tou-> xyg ; ds_shuchu(&tou->hds); free( tou ); tou = p_xyg ; } tou = NULL ;
} extern void jilu( DASHU *p_ds )
{ JIEDIAN **p_t = &tou ; JIEDIAN *p_jd = NULL ; if((p_jd = malloc( sizeof (JIEDIAN ) )) == NULL ){ // 添加节点 printf("无法存储"); exit(!EXIT_SUCCESS); } else{ p_jd->hds = *p_ds ; //把结果写入节点 } while ( *p_t != NULL && ( ds_bijiao(&(*p_t)->hds , p_ds ) == XIAOYU ) ) { //寻找恰当的位置 p_t = &(*p_t)->xyg ; } //加入到链表中 p_jd -> xyg = * p_t ; * p_t = p_jd ; }24.性能改善 这个程序的运行时间主要决定于穷举的过程，所以性能改善显然应该主要考虑这个过程。其中可能的主要因素有：递归调用参数传递、大数运算、算法等。
25.算法改进
在递归过程中考虑一旦累加的“和”应经超过位数或不可能达到位数就提前结束递归
View Code static void xunhuan( const int gssx /*个数上限*/ , const int sz /*关于哪个数字*/, DASHU (*p_hang)[WEISHU + 1] /*指向一行数据*/) { static DASHU he = { { 0 } } ;//用于累加"和" static SHUZI_GESHU sz_gs ; DASHU he_ = he ; //记录累加前的值 if( sz > 0 ){ int i; for( i = 0 ; i <= gssx ; i++ ){ sz_gs[sz] = i ; //记录数字的个数 ds_jiaru ( &he , *p_hang + i ) ; if( ds_chaoguo_W( &he ) == SHI ){ return ; } if(i==gssx && (ds_buzu_W ( &he) == SHI) ){ return ; } xunhuan( gssx - i , sz - 1 , p_hang + 1 ); //选取下一个数字^N的倍数 he = he_ ; //恢复原来的值 } } else{ sz_gs[sz] = gssx ; //记录数字的个数 if( wenhe ( & sz_gs , &he ) == SHI ){ //验算两者是否"吻合" jilu( & he ); //<=>记录结果 } }
}这种办法运行时间只减少了2~3%。
26.不带参数的递归
将xunhuan()中的运算移动到qiongju()，运行时间减少8%左右。
View Code /*2_穷举.c*/ #include "2_穷举.h"
#include "0_问题.h" #define KAISHI JINZHI
#define JIESHU 0 typedef unsigned int SHUZI_GESHU[JINZHI];
//SHUZI_GESHU[d]存储出现在数字组合中数字d的个数 typedef DASHU SHUJUBIAO[JINZHI-1][WEISHU + 1];
//0*(JINZHI-1)^N 1*(JINZHI-1)^N ……WEISHU*(JINZHI-1)^N
//0*(JINZHI-2)^N 1*(JINZHI-2)^N ……WEISHU*(JINZHI-1)^N
//……
//0*(1)^N 1*(1)^N ……WEISHU*(1)^N //static void xunhuan(const int , const int , DASHU (*)[WEISHU + 1] ) ;
static void jianli_sjb ( SHUJUBIAO * * ); //建立数据表
static SF wenhe( SHUZI_GESHU * const , const DASHU * const);
static void zhunbei( int * const , SHUJUBIAO ** const , int * const , DASHU (*(*))[ WEISHU + 1 ]);
static void shouwei( SHUJUBIAO * * const , int * const , DASHU * const ); // 判断*p_he中各数字的个数与*p_sz_gs是否吻合 static SF wenhe( SHUZI_GESHU * const p_sz_gs , const DASHU * const p_he )
{ int sz_gs_he[JINZHI] = { 0 }; //"和"中各数字的个数 if( ds_chaoguo_W(p_he) == SHI //超过W位||不足W位 || ds_buzu_W (p_he) == SHI ){ return FOU ; } ds_qiu_sz_gs( &sz_gs_he , p_he ); //求"和"中各数字的个数 if ( memcmp ( sz_gs_he , *p_sz_gs , sizeof sz_gs_he )==0 ){ return SHI ; } return FOU ;
} //建立数据表 static void jianli_sjb ( SHUJUBIAO * * p_p_sjb )
{ if( (* p_p_sjb = malloc(sizeof(SHUJUBIAO)) ) == NULL ){ exit(!EXIT_SUCCESS); } { int i , j ; for( i = 0 ; i < JINZHI - 1 ; i ++){ ds_fuzhi( *( * * p_p_sjb + i ) + 0 , 0 );//第一列为0 ds_fuzhi( *( * * p_p_sjb + i ) + 1 , 1 );//第二列先赋值为1 for( j = 0 ; j < N ; j ++ ){ //求N次幂 ds_chengyi( *( * * p_p_sjb + i ) + 1 , JINZHI - 1 - i ); } for( j = 2 ; j <= WEISHU ; j ++ ){ (*( * * p_p_sjb + i ))[j] = (*( * * p_p_sjb + i ))[j-1] ; ds_jiaru ( *( * * p_p_sjb + i ) + j , *( * * p_p_sjb + i ) + 1 ) ; } } } } static void zhunbei( int * const p_gssx , SHUJUBIAO ** const p_p_sjb, int * const p_sz , DASHU (*(*p_p_hang))[ WEISHU + 1 ])
{ * p_gssx = WEISHU ; jianli_sjb ( p_p_sjb ) ; //建立数据表 * p_p_hang = **p_p_sjb ; (*p_sz)-- ; } static void shouwei( SHUJUBIAO ** const p_p_sjb , int * const p_sz , DASHU * const p_he )
{ free ( *p_p_sjb ) ; *p_p_sjb = NULL ; * p_sz = KAISHI ; ds_fuzhi( p_he , 0 ); } extern void qiongju( void )
{ static int gssx , sz = JINZHI ; static SHUJUBIAO *p_sjb = NULL ; static DASHU (*p_hang)[ WEISHU + 1 ] ; static DASHU he = { { 0 } } ; //用于累加"和" static SHUZI_GESHU sz_gs ; switch( sz ){ case KAISHI: zhunbei( & gssx , & p_sjb , & sz , & p_hang ); //准备工作 qiongju() ; shouwei( &p_sjb , & sz , &he );//收尾工作 return ; default : { DASHU he_ = he ; //记录累加前的值 int gssx_ = gssx ; int i ; for( i = 0 ; i <= gssx_ ; i ++ ){ ds_jiaru ( &he , *p_hang + i ) ; p_hang++ ; sz_gs[sz--] = i ; gssx = gssx_ - i ; qiongju() ; p_hang -- ; sz ++ ; gssx = gssx_ ; he = he_ ; } } return ; case JIESHU: sz_gs[sz] = gssx ; if( wenhe ( & sz_gs , &he ) == SHI ){ //验算两者是否"吻合" jilu( & he ); //<=>记录结果 } return ; }
}27.减少不必要的大数运算
在递归过程中有些地方的加数为0，没必要。去除这些不必要的加法运算
View Code static void xunhuan( const int gssx /*个数上限*/ , const int sz /*关于哪个数字*/, DASHU (*p_hang)[WEISHU + 1] /*指向一行数据*/) { static DASHU he = { { 0 } } ;//用于累加"和" static SHUZI_GESHU sz_gs ; DASHU he_ = he ; //记录累加前的值 if( sz > 0 ){ int i; for( i = 0 ; i <= gssx ; i++ ){ sz_gs[sz] = i ; //记录数字的个数 if(i!=0){ ds_jiaru ( &he , *p_hang + i ) ; } xunhuan( gssx - i , sz - 1 , p_hang + 1 ); //选取下一个数字^N的倍数 he = he_ ; //恢复原来的值 } } else{ sz_gs[sz] = gssx ; //记录数字的个数 if( wenhe ( & sz_gs , &he ) == SHI ){ //验算两者是否"吻合" jilu( & he ); //<=>记录结果 } }
}很意外，运行时间居然减少了20%左右。
由此可见，大数的运算对性能影响最大，最初的设计用一个int存储一位是有些过于奢侈了。
28.采用新的数据结构
由于前面结果的提示，DASHU采用更紧凑的形式，一个int存储7位，运行时间可减少50%以上
(完)
最新评论