1.【递归】拆分整数 *

一个正整数可以拆分成若干个正整数的和。例如正整数4，可以有4种拆分方法：
4=3+1、4=2+2、4=2+1+1，4=1+1+1+1
用 n 表示待拆分的正整数，用 m 表示从 n 中拆出的最大正整数，则计算对正整数 n 共有多少种拆分方法可以下列递归公式：
0 ( 当 n < 1 或 m < 1 时 )
1 ( 当 n = 1 或 m = 1 时 )
count(n,m)= count(n, n) ( 当 n < m 时 )
count(n, m-1) + 1 ( 当 n=m 时 )
count(n-m, m) + count(n, m-1) ( 其他情况 )

编写递归函数，计算一个正整数有多少种拆分方法。

函数原型如下：

int count( int n, int m)

参数说明：n 待拆分的正整数，m 表示从 n 中拆出的最大正整数；函数返回值是拆分方法数。

例如输入：4， 输出：4

注意：仅提交自编的count函数，不提交main函数。

#include <stdio.h>  
int main()   
{  
   int n, count( );  
   scanf("%d", &n);  
   printf("%d\n", count (n, n-1));    
   return 0;  
}  
int count( int n, int m )     
{   int a = 0;  
        if(n<=1||m<=1)  
        {  
        if(n<1||m<1)  
        {  
                a = 0;  
            }  
        else    if(n==1||m==1)  
        {  
            a = 1;  
         }   
         }   
           
         else  
         {  
          if(n<m)  
          {  
             a = count(n,n);  
          }  
          else  
          {  
            if(n==m)  
            {  
                a = count(n,m-1)+1;  
              }  
              else  
              {  
                a = count(n-m,m) + count(n, m-1);  
              }  
          }  
         }  
         return a;  
}  

2.吃货的烦恼

题目背景

za果然是半吊子水平，竟然选了一个最肥的 Pikachu 做小伙伴。经过实战，za 发现这只 Pikachu 战斗水平并不高，但是体重很可观。于是 za 打算将其往卡比兽方向培养。

其实这只极度肥胖的 Pikachu 也不算很能吃，但不知道为什么连喝水都能胖。这个问题困扰了 za 很久，终于经过彻夜的冥想，za 终于发现其中的奥秘了！（广大吃货朋友的福音）

原来这只 Pikachu 的消化系统很有问题，吃下的食物会在肚子里不断累积增加体重，且会随着时间的增长成倍增加！

即设 Pikachu 初始体重为 w，那么当第 1 秒吃了重量为 p1 的食物后，1s后 Pikachu 体重变为 w+p1；第 2 秒又吃了重量为 p2 的食物，则 2s后 Pikachu 的体重为 w+p1*2+p2。

za 的数学学得很糟糕，不能准确的计算他的 Pikachu 当前重量。小伙伴们，帮帮忙算一算吧！

输入

第一行：Pikachu 的初始体重 w

第二行：Pikachu 吃东西持续的时间 N（1<=N<=30000）

第三行：包含 N 个整数 pi，代表 Pikachu 每一秒吃的食物的重量。由于 Pikachu 实在太胖了，za 把食物重量控制在一个小范围内。（0<=pi<=4）

注：za 作为训练师中的业界良心，保证 Pikachu 的体重不会超过int范围，不会被撑死。

输出

Pikachu 在每一秒后的体重

Example：

Input：

1

4

1 2 3 4

Output：

2 5 11 21

第1s：1 + 1*1；

第2s：1 + 1*2 + 2*1；

第3s:   1 + 1*3 + 2*2 + 3*1;

第4s：1 + 1*4 + 2*3 + 3*2 + 4*1；

#include <stdio.h>  
  
int main(int argc, char** argv) {  
    int m0, n, a[30005], m1, i, j;  
    scanf("%d", &m0);  
    scanf("%d", &n);  
    for(i = 0; i<n;i++)  
    {  
        scanf("%d", &a[i]);  
    }  
    for(i = 0; i<n;i++)  
    {  
        for(j = 0;j<=i;j++)  
        {  
            m0+=a[j];  
        }  
    if(i<n-1)  
    {  
            printf("%d ", m0);  
        }  
        else  
        {  
                printf("%d\n", m0);  
        }  
    }  
      
}  

3.【应用】字符压缩

通过键盘输入一个字符串，请编写一个字符串压缩程序，将字符串中连续出现的重复小写字母（a～z）进行压缩，并输出压缩后的字符串。压缩规则如下：

1）仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc"。

2）压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。

【输入】字符串

【输出】压缩后的字符串

示例。输入："cccddecc”，输出："3c2de2c”。输入："adef”，输出："adef”。输入："pppppppp”，输出："8p”。

#include<stdio.h>    
#include<string.h>    
int main()    
{    
    char a[100000],b[100000];    
    int i,ct=0,j=0,cj[10000];    
    char c;     
    gets(a);    
    for(i=0,c=a[0]+1;a[i];i++)    
    {    
        if(a[i]>='a'&&a[i]<='z'&&a[i]==c)    
        {ct++;}    
        else if(a[i]>='a'&&a[i]<='z'&&i<strlen(a)-1&&a[i]==a[i+1]&&a[i]!=c&&ct==0)    
        {    
            ;    
        }    
        else    
        {    
            if(ct==0)    
            {    
                b[j]=a[i];j++;    
            }    
            else    
            {   cj[j]=ct+1;    
                b[j]=-1;    
                b[j+1]=a[i-1];    
                if(a[i+1]&&a[i]==a[i+1]&&a[i]>='a'&&a[i]<='z')    
                {    
                    j=j+2;    
                }    
                else    
                {    
                j=j+2;    
                b[j]=a[i];j++;}    
            }    
            ct=0;    
        }    
        c=a[i];    
    }    
    if(ct>0)    
    {    
           cj[j]=ct+1;    
                b[j]=-1;    
                b[j+1]=a[i-1];    
                j=j+2;    
    }    
    b[j]='\0';    
    for(i=0;b[i]!='\0';i++)    
    {    
        if(b[i]==-1)    
        {    
            printf("%d",cj[i]);    
        }    
        else    
        {    
            printf("%c",b[i]);    
        }    
    }    
    printf("\n");    
}  

4.【链表】删除负数*

一个带有表头节点的链表中，链表的每个节点保存了非零的整型数据。现请编写函数删除已有的链表中所有数值小于0的节点。

说明：（1）用带表头的单向链表的方式保存数据，每一个节点的数值域保存一个非零整型数。
（2）预设代码包括主函数、建立链表函数、输出链表函数，请编写删除链表中所有数值小于0的节点的函数。

结构的定义：

struct node

{ int data; struct node *next;

};

typedef struct node NODE;
typedef struct node * PNODE;

删除所有无效数值结点的函数原型：void deleteneg(PNODE head)，

其中：参数head是带有头结点的单向链表的头指针。

程序输入：在建立链表时，每次插入到头结点后的结点数据，以0为结束。

#include <stdio.h>  
#include <stdlib.h>  
    
struct node    
{  
    int data;    
    struct node * next;    
};    
    
typedef struct node NODE;   
typedef struct node * PNODE;  
   
PNODE constructlist( PNODE head, int num );  
void outlist( PNODE );  
void deleteneg( PNODE );   
  
int main( )    
{   int num=1;    
    PNODE head;    
    
    head = (PNODE)malloc( sizeof(NODE) );    
    head->next = NULL;    
    head->data = -1;    
    
    while ( num!=0 )    
    {   scanf("%d", &num);    
        if ( num!=0 )    
           constructlist (head, num);    
    }    
    deleteneg( head );  
    outlist( head );    
    return 0;    
}    
    
PNODE constructlist( PNODE head, int num )  
{   PNODE p;  
    p = (PNODE)malloc( sizeof(NODE) );   
    p->data = num;  
    p->next = head->next;   
    head->next = p;  
    return head;  
}  
  
void outlist( PNODE head )    
{   PNODE p;    
    p = head->next;    
    while ( p != NULL )    
    {   printf("%d\n", p->data);    
        p = p->next;    
    }    
}    
void deleteneg( PNODE head )    
{      
   PNODE p,q;      
   q = head;  
   p = head->next;     
   for(;p; p = p->next)  
   {  
    if(p->data<0)  
    {  
        q->next = p->next;  
    }  
    else  
    {  
        q = p;  
  
    }  
}  
}