小学数学题,你会吗?

时间:2022-04-27 21:53:40

小学数学题,你会吗?

一日,某小学生问作业:“将16分解为若干素数的和,求这些素数积的最大值”。不禁被吓了一跳。怎么小学生的数学题变得这么难了?
  细细询问,小学生没学不等式,没学数学归纳法……。那么只能用最笨的办法——穷举,一个个地试的办法来解决。
  穷举之道,在于一一举来,不多不少;而不多不少,则在于有条有理,从容不乱。
  小于16的素数依次为:2,3,5,7,11,13。显然,最大积是16和{2,3,5,7,11,13}的函数,将这个最大积记为
    F(16,{2,3,5,7,11,13})
  该最大积中可能有素因子2也可能没有,因此

    F(16,{2,3,5,7,11,13}) = 
     MAX ( 
               2 * F(14 ,{2,3,5,7,11,13}) ,
               F(16 ,{3,5,7,11,13} ) ,
           )
  同理,
    F(14,{2,3,5,7,11,13}) = 
     MAX ( 
               2 * F(12 ,{2,3,5,7,11,13}) ,
               F(14 ,{3,5,7,11,13} ) ,
           )

    F(16,{3,5,7,11,13}) = 
     MAX ( 
               3 * F(3 ,{2,3,5,7,11,13}) ,
               F(16 ,{5,7,11,13} ) ,
           )
    ……
  由此不难看出这构成了一个递归过程,终止的条件为F(n,{})中的素数集合为空或n<=0。
  下面用C语言描述这个过程。
  用程序解决问题显然不应该只解决分解16这样单独的问题,而应该至少能解决一类问题。为此将问题描述为:
  将正整数n分解为若干素数的和,求这些素数积的最大值。

小学数学题,你会吗?
#include <stdio.h>

void input( unsigned * );
unsigned maxmul( unsigned , 素数集合类型 );
unsigned maxmul_(  unsigned , 素数集合类型 );
unsigned max( unsigned , unsigned );

int main( void )
{
   
   unsigned n ;
   素数集合类型 素数集合; //这里需要一个素数集合;

   input( &n );                             //输入n   
   printf("%u\n", maxmul( n , 素数集合 ) ); //输出最大积

   return 0;
}

unsigned max( unsigned u1 , unsigned u2 )
{
   return u1 > u2 ? u1 : u2 ;
}

unsigned maxmul_( unsigned n , 素数集合类型 素数集合 )
{
   if ( 素数集合为空 ||  n < 素数集合中的最小元素 )
   {
      return 0;
   }
   if ( n == 素数集合中的某个元素 )
   {
      return n;
   }
   return max (
                 素数集合中的某元素 * maxmul_(  n - 素数集合中的某元素 , 素数集合 ) ,
                 maxmul_( n , 素数集合删掉一个元素 ) 
              );
}

unsigned maxmul( unsigned n , 素数集合类型 素数集合 )
{
   if ( n < 4u ) // 小于4的情况无解
      return 0;

   return maxmul_( n , 素数集合 );
}

void input( unsigned * p )
{
  puts( "输入n:" );
  scanf( "%u" , p );   
}
小学数学题,你会吗?

   至此,还需要给出不大于n的素数集合。由于不清楚不大于n有多少素数,所以用数组表示这个集合显然不现实,即使用C99的VLA也不够好。
  那么只好用链表。问题就成了给出不大于正整数n的素数链表。链表用下面的数据结构描述:

小学数学题,你会吗?
typedef 
struct prime_list
   {
      unsigned prime;
      struct prime_list * next;
   } 
* P_LIST;
小学数学题,你会吗?

   在main()中定义这个链表:

P_LIST pr_list = NULL ;

   根据n求得这个链表

pr_list = build( n ); 

   令我没想到的是这个函数不那么容易写,稍不留神就错。你们体会下!

小学数学题,你会吗?
typedef 
struct prime_list
   {
      unsigned prime;
      struct prime_list * next;
   } 
* P_LIST;

typedef
enum 
   { 
      NO ,
      YES, 
   } 
YESNO ;

P_LIST build( unsigned  );
void build_( P_LIST * , P_LIST * , unsigned , unsigned );
YESNO be_prime( unsigned , P_LIST );
void add ( P_LIST * * , unsigned ) ;
void my_malloc( P_LIST * );

void my_malloc( P_LIST * pp )
{
   if ( ( * pp = malloc( sizeof (* * pp) )) == NULL )
      exit(1);
}

void add ( P_LIST * * ppp_e, unsigned const num ) 
{
   my_malloc( * ppp_e ); 
   ( * * ppp_e ) -> prime = num ;
   ( * * ppp_e ) -> next  = NULL;
   * ppp_e = & ( * * ppp_e ) -> next ;
}


YESNO be_prime( unsigned n , P_LIST p )
{
   if ( n == 2u || p == NULL )
   {
      return YES ;
   }
   if ( n % p -> prime == 0u )
   {
      return NO ;
   }
   return be_prime( n , p -> next );
}

void build_( P_LIST * pp_b , P_LIST * pp_e , 
             unsigned num , unsigned n )
{
   if( num > n )
   {
      return ;
   }
   if ( be_prime( num , *pp_b ) == YES  )
   {
      add ( &pp_e , num ) ; //将num加入链表
   }
   build_( pp_b ,  pp_e , num + 1u , n ) ; 
}

P_LIST build( unsigned n )//建立不大于n的有序素数链表 
{
   P_LIST head = NULL ;
   build_( &head , &head , 2u , n );  //从2开始
   return head;
}
小学数学题,你会吗?

   最后是完整的代码。

小学数学题,你会吗?  View Code

#include <stdio.h>

typedef
struct prime_list
{
unsigned prime;
struct prime_list * next;
}
* P_LIST;

typedef
enum
{
NO ,
YES,
}
YESNO ;

void input( unsigned * );
P_LIST build( unsigned );
void build_( P_LIST * , P_LIST * , unsigned , unsigned );
YESNO be_prime( unsigned , P_LIST );
void add ( P_LIST * * , unsigned ) ;
void my_malloc( P_LIST * );
unsigned maxmul( unsigned , P_LIST );
unsigned maxmul_( unsigned , P_LIST );
unsigned max( unsigned , unsigned );
void my_free( P_LIST );

int main( void )
{

unsigned n ;
P_LIST pr_list = NULL ;

input( &n ); //输入n
pr_list = build( n ); //准备素数表
printf("%u\n", maxmul( n , pr_list ) ); //输出
my_free( pr_list );

return 0;
}

void my_free( P_LIST p )
{
if ( p != NULL )
{
free( p -> next );
free( p );
}
}

unsigned max( unsigned u1 , unsigned u2 )
{
return u1 > u2 ? u1 : u2 ;
}

unsigned maxmul_( unsigned n , P_LIST p )
{
if ( p == NULL || n < p->prime )
{
return 0;
}
if ( n == p->prime )
{
return n;
}
return max (
p -> prime * maxmul_( n - p->prime , p ) ,
maxmul_( n , p -> next )
);
}

unsigned maxmul( unsigned n , P_LIST p )
{
if ( n < 4u )
return 0;

return maxmul_( n , p );
}

void my_malloc( P_LIST * pp )
{
if ( ( * pp = malloc( sizeof (* * pp) )) == NULL )
exit(1);
}

void add ( P_LIST * * ppp_e, unsigned const num )
{
my_malloc( * ppp_e );
( * * ppp_e ) -> prime = num ;
( * * ppp_e ) -> next = NULL;
* ppp_e = & ( * * ppp_e ) -> next ;
}


YESNO be_prime( unsigned n , P_LIST p )
{
if ( n == 2u || p == NULL )
{
return YES ;
}
if ( n % p -> prime == 0u )
{
return NO ;
}
return be_prime( n , p -> next );
}

void build_( P_LIST * pp_b , P_LIST * pp_e ,
unsigned num , unsigned n )
{
if( num > n )
{
return ;
}
if ( be_prime( num , *pp_b ) == YES )
{
add ( &pp_e , num ) ; //将num加入链表
}
build_( pp_b , pp_e , num + 1u , n ) ;
}

P_LIST build( unsigned n )//建立不大于n的有序素数链表
{
P_LIST head = NULL ;
build_( &head , &head , 2u , n ); //从2开始
return head;
}

void input( unsigned * p )
{
puts( "输入n:" );
scanf( "%u" , p );
}

  运行结果:

输入n:
16
324

题外话:

 

  从数学的角度看,这个题目并不难。只要运用初中数学知识,就不难分析出,对于大于3的正整数n的最大素数积,当n为

    6k型正整数时,分为2k个3积最大;
    6k+1型正整数时,分为2k-1个3、2个2积最大;
    6k+2型正整数时,分为2k个3、1个2积最大;
    6k+3型正整数时,分为2k+1个3积最大;
    6k+4型正整数时,分为2k个3、2个2积最大;
    6k+5型正整数时,分为2k+1个3、1个2积最大。
  结论用数学归纳法很容易证明。参见http://bbs.chinaunix.net/thread-4088334-2-1.html

 
 
 
标签:  C语言链表递归