本文主要是介绍UVA 1350 - Pinary(数论+递推），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：1350 - Pinary
题意：二进制数，不能有连续的1，给定第n个数字，输出相应的二进制数
思路：先是递推，求出由n位组成的数字中有几个满足条件
dp[i] = dp[i - 1] + dp[i - 2]，考虑最后一位放0和倒1位放0的情况。
然后用一个sum[i]记录满足<=i位一共的情况
接着利用二分找到给定的n > sum[i - 1]，i的最大值，这个就是所求的答案的最高位。
因为如果这位放1，那么就会一共多sum[i - 1] + 1个数，那么就还需要添加n - (sum[i - 1] + 1)，就这样一位一位往后推，遇到能放1的就尽量放1，其余的就是0
代码：
#include <stdio.h>
#include <string.h>int t, n, num[40], sum[40];void init() {num[1] = num[2] = 1;sum[1] = 1; sum[2] = 2;for (int i = 3; i < 40; i++) {num[i] = num[i - 1] + num[i - 2];sum[i] = sum[i - 1] + num[i];}
}int find(int n) {int l = 0, r = 40;while (l < r) {int mid = (l + r) / 2;if (sum[mid] >= n)r = mid;elsel = mid + 1;}return l;
}int main() {init();scanf("%d", &t);while (t--) {scanf("%d", &n);int len = find(n);for (int i = len; i > 0; i--) {if (n > sum[i - 1]) {printf("1");n = n - sum[i - 1] - 1;}else printf("0");}printf("\n");}return 0;
}这篇关于UVA 1350 - Pinary(数论+递推）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
