UVA 10183 How Many Fibs?

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

题意：求[a,b]之间的Fibonacci numbers，范围达到10^100，用到了高精度，然后测试了一下，到第500个的时候，长度就已经是105了，所以我们只要计算到第500个就行了，顺便复习了高精度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;char fib[550][170];void Add(char *a,char *b,char *res){int lena = strlen(a),lenb = strlen(b);int x,i,y = 0;for (i = 0; i < lena || i < lenb || y; i++){x = y;if (i < lena)x += a[i] - '0';if (i < lenb)x += b[i] - '0';y = x / 10;res[i] = x % 10 + '0';}res[i] = '\0';
}void Reverse(char *result){int len = strlen(result);int b = len>>1;for (int i = 0; i < b; i++){char temp = result[i];result[i] = result[len-1-i];result[len-1-i] = temp;}
}int cmp(char *a,char *b){int lena = strlen(a);int lenb = strlen(b);if (lena < lenb)return 1;if (lena > lenb)return -1;if (lena == lenb){for (int i = 0; i < lena; i++)if (a[i] < b[i])return 1;else if (a[i] > b[i])return -1;}return 0;
}int main(){fib[1][0] = '1';fib[2][0] = '2';Reverse(fib[1]);Reverse(fib[2]);for (int i = 3; i <= 500; i++)Add(fib[i-1],fib[i-2],fib[i]);for (int i = 1; i <= 500; i++)Reverse(fib[i]);char a[200],b[200];while (scanf("%s%s",a,b) != EOF){if (a[0] == '0' && b[0] == '0')break;int count = 0;for (int i = 1; i <= 500; i++){if (cmp(fib[i],b) < 0)break;if (cmp(a,fib[i]) >= 0)count++;}printf("%d\n",count);}return 0;
}

这篇关于UVA 10183 How Many Fibs?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---