C语言经典题目及解题思路

6、【问题描述】编写一个 c程序，把下列数组延长到第 50项：
1， 2， 5， 10， 21， 42， 85， 170， 341， 682
【思路】由给定的数组元素可以看出偶数项是前一项的 2倍，奇数项是前一项的 2倍加 1。
即  ，这是一中递推关系由前项推出后项，此题可以通过递推关系求解。
       递推解题和迭代解题是很相似的，递推是通过其他变量来演化，而迭代则是通过自身不断演化。递推法的运用也有三个关键：

寻找递推关系。这是最重要的问题。递推关系有解析和非解析两种。解析递推关系是指能用一般数学公式描述的关系，也称递推公式。例如，本题的递推关系就是解析的。非解析递推关系是指不能用一般的数学公式描述的关系，这类关系的描述，也许本身就是一个过程。这类问题一般比较复杂，要结合其他的策略如分治法来解决。
递推关系必须有始基，即最小子解（针对初始规模的子解的值），没有始基，递推计算就不能开始。例如本题 a1=1就是始基。
递推计算。即根据递推关系进行递推计算。递推计算可以由递归解析和非递归两种，递归计算是采用递归法，其形式是自顶向下，而非递归则是自底向上。本题是非递归的。
解此题还须注意一点：数列的项必须定义为 double型，因为延长到第 50项如果定义为 int or float型，数列的项会被截断即超过 int和 float的表示范围。
【代码】

cCODE:
 
#include
#include

int main (int argc, char **argv)
{

    double a1=1,a=0;
    int i=1;
    while(i<=50)
    {
        printf("%.0lf ",a1); //'.0’ is just for do not output the decimal place
        i++;
        if(i%2==1)
            a=2*a1+1;
        else
            a=2*a1;
        a1=a;  
    }                           
    system("PAUSE");
    return 0;
}
 

【程序输入输出】
No input；
Output：
1 2 5 10 21 42 85 .......（略）

7、
【问题描述】 用递归算法实现求一个数组中的最大元素。
【思路】解决递归问题可以分为两个部分，第一部分是一些特殊（基础）情况，用直接法解，即始基；第二部分与原问题相似，可用类似的方法解决（即递归），但比原问题的规模要小。
     本题显然始基是a[0],关键是要找出递归关系，定义一个函数int max(int a[],int n)，其中整型a[]是一个数组，n是数组长度减1，即数组最大有效元素的下标，因为c语言中数组元素下标是从0开始的。

如果0==n，则a[0]就是最大的元素
如果n>0，则先求出a[0]到a[n-1]的最大元素，然后与a[n]比较，较大者即为最大元素。其中a[0]到a[n-1]又可以用这种方式求，此时需要将a[0],a[1]...a[n-1]看成一个由n-1个元素构成的一维数组。
【代码】

cCODE:
 
#include
#include

int max(int a[],int n);

int main (int argc, char **argv)
{   
    int a[]={1,2,3,4,5,6,7,6};
    printf("The max element is %d!\n",max(a,7)); 
    /*caution:he length of a is 8,but the argument is 7*/             
    system("PAUSE");
    return 0;
}

int max(int a[],int n)
{
    if(0==n)
        return a[n];
    else   
        return (a[n]>max(a,n-1)?a[n]:max(a,n-1));  
}

【程序输入输出】
no input;
output:
The max element is 7!

8、
【问题描述】自然数的拆分：任何一个大于1的自然数N，总可以拆分成若干个自然数之和，并且有多种拆分方法。例如自然数5，可以有如下一些拆分方法：
5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=1+4
5=2+3
【思路】自然数的拆分可以用回溯法。
知识点 ： 回溯法解题时，对任一解的生产，一般采用逐步扩大解的方式。每进行一步，都试图在当前部分解的基础上扩大该部分解。扩大时，首先检查扩大后是否违反了约束条件，若不违反，则扩大之，然后继续在此基础上按照类似的方法进行，直至为完全解；若违反，则放弃该步以及它生成的部分解，然后按照类似的方法尝试其他可能的扩大方式，直到已经尝试了所有的扩大方式。
回溯法解题通常包含以下三个步骤：

针对所给问题，定义问题的解空间；如本题对 5的拆分来说， 1<=拆分的数 <=5。
确定易于搜索的解空间结构；如本题对 5的拆分来说，用 x[]数组来存储解，每个数组元素的取值范围都是 1<=拆分的数 <=5，从 1开始搜索直到 5。
搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。如本题对 5的拆分来说，为了避免重复， x>=x[j](i>j)，如 x[]={2,3}满足条件而 x[]={3,2}就不满足条件不是可行解即无效。
回溯法通常有两种实现方式，一种是递归的方式，另一种是迭代的方式。在此就用递归方式，当然迭代的方式也可以。 　　
【代码】

cCODE:
 
#include
#include

void splitN(int n,int m);//n是需要拆分的数， m是拆分的进度。
int x[1024]={0},total=0 ;//total用于计数拆分的方法数， x[]用于存储解

int main()
{
    int n ;
    printf("please input the natural number n:");
    scanf("%d",&n);
    splitN(n,1);
    printf("There are %d ways to split natural number %d.\n",total,n);
    system("PAUSE");
    return 0 ;
}

void splitN(int n,int m)
{//n是需要拆分的数， m是拆分的进度。
    int rest,i,j;   
    for(i=1;i<=n;i++)
    {//从 1开始尝试拆分。        
        if(i>=x[m-1])
        {//拆分的数大于或等于前一个从而保证不重复
            x[m]=i ;//将这个数计入结果中。            
            rest=n-i ;//剩下的数是 n-i，如果已经没有剩下的了，并且进度 (总的拆分个数 )大于 1，说明已经得到一个结果。
            if(rest==0&&m>1)
            {
                total++;
                printf("%d\t",total);
                for(j=1;j                {
                    printf("%d+",x[j]);
                }
                printf("%d\n",x[m]);
            }
            else
            {
                splitN(rest,m+1);//否则将剩下的数进行进度为 m+1拆分。
            }
            x[m]=0;//取消本次结果，进行下一次拆分。环境恢复，即回溯
        }
    }
} 

【程序输入输出】

input:
please input the natural number n:5
output:
1       1+1+1+1+1
2       1+1+1+2
3       1+1+3
4       1+2+2
5       1+4
6       2+3
There are 6 ways to split natural number 5.

9、
【问题描述】用递归函数求解两个正整数的最大公约数的过程。
【思路】此题不需太多的思考就是运用欧几里得算法（ Euclid’s algorithm）。

  摘自《 The Art  of Computer Programming》 volume 1：
  (Euclid’s algorithm )Give two postive  integers m and n, find their greatest common divisor, that is ,the largest  positive integer that evenly divide both m and n.
  Step1.[Find remainder.]Divide m by n and  let r be the remainder.(We will have 0<=r  Step2.[Is it zero?]If r=0,the algorithm  terminates; n is the answer.
  Step3.[Reduce.]Set m=n,n=r, and go back  to Step1.
  

【代码】

  cCODE: 
 
  #include
  #include
  int GCD(int m,int n);
  /*function is to find the greatest common divisor between mand n*/
  int main (int argc, char **argv)
  {   
      int m,n,temp;
      printf("Please input m and n:\n");
      scanf("%d %d",&m,&n);   
      if(m      {/*This is just ensure m>n*/
           temp=m;
           m=n;
           n=temp; 
      }
      printf("The greatest common divisor of (%d,%d) is  %d!\n",m,n,GCD(m,n));          
      system("PAUSE");
      return 0;
  }
 
  int GCD(int m,int n)
  {
      if(m%n==0)
           return n;
      else return GCD(n,m%n);
  }
  

【程序输入输出】
Please input m and n:
10 5
The greatest common divisor of (10,5) is 5!

10、

【问题描述】 已知Ackerman函数对于整数m>=0和n>=0有如下定义：

ack(0,n)=n+1

ack(m,0)=ack(m-1,1)

ack(m,n)=ack(m-1,ack(m,n-1))

【思路】此题明显用递归方法解，由上述定义可得递归公式如下：

          | n+1,                当m=0时；

ack(m,n)= | ack(m-1,1),          当n=0时；

          | ack(m-1,ack(m,n-1)), 其他情况。

【代码】

  cCODE: 
 
  #include
  #include
  int ack(int m,int n);
  int main (int argc, char **argv)
  {   
      int m,n;
      printf("Please input m and n:\n");
      scanf("%d %d",&m,&n);
      printf("The result of ack(%d,%d) is  %d!\n",m,n,ack(m,n));           
      system("PAUSE");
      return 0;
  }
 
  int ack(int m,int n)
  {
      if(0==m)
           return n+1;
      else if(0==n)
           return ack(m-1,1);
      else return ack(m-1,ack(m,n-1));
  }
  

【程序输入输出】
example 1:
input:
Please input m and n:
0 5
ouput:
The result of ack(0,5) is 6!
example 2:
Please input m and n:
4 0
The result of ack(4,0) is 13!
example 3:
Please input m and n:
2 3
The result of ack(2,3) is 9!

//------------------------------------------------------------------------------------//

1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表h；

[Copy to clipboard] [ - ]
CODE:
#include
#include
#include

#define QUIT 999

typedef struct node
{
  int num;
  struct node* next;
   }NODE;
  
int create_list(NODE** head)
{
  int num;
  int i = 0;
  NODE* p = NULL;
  NODE* q = NULL;
 
  *head = (NODE*)malloc(sizeof(NODE));
  if(*head == NULL)
   {
     printf("head malloc error\n");
     return -1;
     }
   (*head)->next = NULL;
  
   printf("input %d to end add list\n",QUIT);
   while(1)
   {
     p = *head;
     q = (NODE*)malloc(sizeof(NODE));
     if(q == NULL)
     {
      printf("head malloc error\n");
      return -1;
     }
     i++;
     printf("Now Please input num %d:\t",i);
     scanf("%d",&num);
     if(num == QUIT)
       {
         printf("end create list\n");
         break;
        }
     q->num = num;
     while((p->next != NULL) && (p->next->num < num))
      {
        p = p->next;
       }
       
     q->next = p->next;
     p->next = q;
  
    }
   return 0;
}

NODE* merge_list(NODE* head1,NODE* head2)
{
     assert(head1 != NULL);
     assert(head2 != NULL);
    
    
     NODE* head = (NODE*)malloc(sizeof(NODE));
     if(head == NULL)
     {
       printf("head malloc error\n");
       return NULL;
     }
    
     NODE* head_tmp = head;
     NODE* p1 = head1->next;
     NODE* p2 = head2->next;
    
     while((p1 != NULL) && (p2 != NULL))
       {
         printf("p1 data is %d\t p2 date is %d\n",p1->num,p2->num);
         if(p1->num < p2->num)
           {
             printf("copied %d\n",p1->num);
             system("PAUSE");
             head_tmp->next = p1;
             p1 = p1->next;
             }
          else
           {
             printf("copied %d\n",p2->num);
             system("PAUSE");
             head_tmp->next = p2;
             p2 = p2->next;
             }
            head_tmp = head_tmp->next;
         }
        
     if(p1 == NULL)
        {
         head_tmp->next = p2;
         printf("asdas copied:\n");
         print_list(head_tmp);
        }
     else
       {
         head_tmp->next = p1;
         printf("asdas copied:\n");
         print_list(head_tmp);
        }
     return head;
  }
int print_list(NODE* head)
{
   assert(head != NULL);
   NODE* p = head;
   while(p->next != NULL)
    {
      printf("%d\t",p->next->num);
      p = p->next;
      }
   printf("\n");
}

int main(int argc, char *argv[])
{
  NODE* head1 = NULL;
  NODE* head2 = NULL;
 
  create_list(&head1);
  create_list(&head2);

  printf("list1 is:\n");
  print_list(head1);
  printf("list2 is:\n");
  print_list(head2);
  printf("merged list is:\n");
  print_list(merge_list(head1,head2));
   
  system("PAUSE");   
  return 0;
}

2编写算法，从10亿个浮点数当中，选出其中最大的10000个。

[Copy to clipboard] [ - ]
CODE:
#include
#include
#include

//#define INIT 10000

#define INIT 5

//#define TOTAL 100000000

#define TOTAL 10

static int count = 0;

typedef struct tree
{
   int num;
   struct tree* parent;
   struct tree* lchild;
   struct tree* rchild;
  }TREE;
 
TREE* add_tree(TREE** T, TREE* parent, int num)
{
  if(*T == NULL)
   {
     *T = (TREE*)malloc(sizeof(TREE));
     if(*T == NULL)
      {
        printf("malloc error\n");
        return NULL;
        }
        printf("added %d\n",num);
       (*T)->num = num;
       (*T)->parent = parent;
       (*T)->lchild = NULL;
       (*T)->rchild = NULL;
     }
    else if((*T)->num < num)
       return add_tree(&(*T)->rchild,*T,num);
    else
       return add_tree(&(*T)->lchild,*T,num);
}

int midwalk(TREE* T)
{
  if(T!=NULL)
   {
     midwalk(T->lchild);
     count++;
     if(count%10 == 0)
      {
        count = 0;
        printf("%d\n",T->num);
       }
     else
       printf("%d\t",T->num);
    
     midwalk(T->rchild);
     }
   return 0;
}

int tree_out(TREE** T)
{
  int num = 0;
  TREE* p = NULL;
  TREE* q = NULL;
  TREE** tmp = T;
  TREE* tmp1 = *T;
 
  printf("tmp is %p\ntmp1 is %p\n",*tmp,tmp1);
   if(*tmp == NULL)
    {
      printf("sorry the tree is empty\n");
      return -1;
      }
    if((*tmp)->lchild == NULL)
    {
      q = *tmp;
      num = q->num;
      *tmp = (*tmp)->rchild;
      printf("now head is %d\n",q->num);
      free(q);
      q = NULL;
      return num;
      }
    #if 1
    while(tmp1->lchild != NULL)
     {
        p = tmp1;
        tmp1 = tmp1->lchild;
      }
     p->lchild = tmp1->rchild;
    num = tmp1->num;
    free(tmp1);
   #endif
   #if 0
   while((*tmp)->lchild != NULL)
     {
        p = *tmp;
        *tmp = (*tmp)->lchild;
      }
     p->lchild = (*tmp)->rchild;
    num = (*tmp)->num;
    free(*tmp);
   #endif
    return num;
}

int minimum(TREE* T)
{
  while(T->lchild != NULL)
   {
     T = T->lchild;
     }
   return T->num;
}
   
int main(int argc, char *argv[])
{
  int i = 0;
  int num = 0;
  double j = INIT;
  int mini = 0;
 
 
  TREE* T = NULL;
  srand( (unsigned)time( NULL ) );

  for(i=0;i  {
    num = rand();
    add_tree(&T, NULL, num);
   }
   midwalk(T);
  
   mini = minimum(T);
  for(j=INIT;j  {
    num = rand();
    if(num > mini)
      {
       tree_out(&T);
       add_tree(&T, NULL, num);
       mini = minimum(T);
      }
   }
  
  midwalk(T);
  system("PAUSE");   
  return 0;
}