hdu_1865 1sting

本文主要是介绍hdu_1865 1sting，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1865

分析：

       题意分析：给你一些数串（只是由1，2组成），这些1两两相加（最大加到2）组成新的数，有几种。输入的数都是1.

       题解分析：

              设有n个1，可以构成f(n)种。则加一个1的时候，前面n种仍然成立 f(n+1)=f(n)+?;

               第n+1个1和第n个1相加构成2，前面n-1个1可以组合的个数。  f(n+1)=f(n)+f(n-1);

              故，递推公式： ans[i]=ans[i-1]+ans[i-2];

              因为n很大，__int64 都会溢出，用数组模拟或Java.

我的代码：

#include<stdio.h>
#include<string.h>
typedef __int64 LL;
int ans[205][501];
void add(int k)  //模拟加。
{int r=0;for(int i=500;i>=0;i--){r=ans[k-1][i]+ans[k-2][i]+r;ans[k][i]=r%10;r/=10;}
}
int main()
{char str[250];ans[1][500]=1;ans[2][500]=2;for(int i=3;i<=205;i++) add(i);int t;scanf("%d",&t);while(t--){scanf("%s",str);int len=strlen(str);int j;for( j=0;j<=500;j++) if(ans[len][j]) break;for(;j<=500;j++) printf("%d",ans[len][j]);printf("\n");}return 0;
}

总结：练习的时候本想用Java的，一时不会开Java的数组了 囧rz。。

练习后，又试了下Java.

import java.math.BigInteger;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner cin = new Scanner(System.in);BigInteger[] ans = new BigInteger[205]; //忘记是这样开数组的。。ans[1]=BigInteger.valueOf(1);ans[2]=BigInteger.valueOf(2);for(int i=3;i<=200;i++) ans[i]=ans[i-1].add(ans[i-2]);int t=cin.nextInt();for(int i=0;i<t;i++){String s;s=cin.next();  //不能用nextline();int n=s.length();System.out.println(ans[n]);}}
}

      

这篇关于hdu_1865 1sting的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---