首页 > 代码库 > ACM每日一练(猴子吃桃问题)

ACM每日一练(猴子吃桃问题)

2024-07-14 14:48:22   221人阅读

描述
有一堆桃子不知数目，猴子第一天吃掉一半，又多吃了一个，第二天照此方法，吃掉剩下桃子的一半又多一个，天天如此，到第m天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？ (m<29)
输入
第一行有一个整数n,表示有n组测试数据（从第二行开始，每一行的数据为：第m天）；
输出
每一行数据是桃子的总个数
样例输入
2
3
11
样例输出
22
6142

普通解法

分析:  倒推  前一天的桃子总数 与后一天的桃子总数关系
递推公式是 a[m-1]=(a[m]+1)*2;
我们可以通过循环m次求出第一天的桃子总数。
#include <stdio.h>
main()
{
 int i,n,m,sum;
 scanf("%d",&n);
 while(n--)
 {
  sum=1;
  scanf("%d",&m);
  for (i=m;i>0;i--)
   sum=2*(sum+1);
  printf("%d\n",sum);
 }
}

递归解法
将前面的for循环改为递归调用
#include <stdio.h>
int sum(int n)
{
 if (n==0) return 1;
 else return 2*(sum(n-1)+1);
}
main()
{
 int m,n;
 scanf("%d",&m);
 while(m--)
 {
  scanf("%d",&n);
  printf("%d\n",sum(n));
 }
}

最简解法
分析
a[0]=1
a[1]=(a[0]+1)*2
...
a[n-1]=(a[n-2]+1)*2
a[n]=(a[n-1]+1)*2
由上可求出该数列的通项公式为a[n]=3*(pow(2,n))-2  

则程序可以改进为
#include <stdio.h>
main()
{
 int m,n;
 scanf("%d",&m);
 while(m--)
 {
  scanf("%d",&n);
  //3左移n位 相当于 3*pow(2,n)
  printf("%d\n",(3<<n)-2);
 }
}


描述
给你一个乱序的字符串,里面包含有小写字母(a--z)以及一些特殊符号，请你找出所给字符串里面所有的小写字母的个数， 拿这个数对26取余，输出取余后的数字在子母表中对应的小写字母(0对应z,1对应a，2对应b....25对应y)。
输入
第一行是一个整数n(1<n<1000)表示接下来有n行的字符串m(1<m<200)需要输入
输出
输出对应的小写字母 每个小写字母单独占一行
样例输入
2
asdasl+%$^&ksdhkjhjksd
adklf&(%^(alkha
样例输出
q
j

#include <stdio.h>
main()
{
 int i,n;
 char c[198];
 scanf("%d",&n);
 while(n--)
 {
  int count=0;
  scanf("%s",c);
  for(i=0;c[i]!='\0';i++)
   if (c[i]>96 && c[i]<123) count++;
  if (count%26==0) printf("z\n");
  else printf("%c\n",count%26+96);
 }
}


联系
我们