杂题

您所在的位置：网站首页 › alice的01串 › 杂题

杂题

2024-07-16 15:27| 来源: 网络整理| 查看: 265

杂题中大 1. 不连续1的子串题目描述

串只包含0或者1，给定一个数字，输出以此为长度的01串不含连续1的串的个数。如输入3，则输出5，因为长度为3的01串不含连续1的串包括000, 001, 010, 100, 101。

解题思路

思路1：

(暴力，较复杂) 将0-n的数转成二进制数，用数组存储此二进制数；遍历此数组，判断1后有没有跟1，若有则break，遍历下一个数；若遍历完数组没有break，则num++。

思路2：将’1’或’0’放置在长度固定为n的数组中，不能有连续的’1’，看有多少种放法。

若放i个’1’，则另外有n-i个0，相当于在i-1个’0’的周围放’1’，有多少种放法；等于组合数C(n-i+1, i)。遍历i从0-n，累加种数即可。源代码

思路1：

#include #include #include #include using namespace std; char a[32] = {0}; char* toRadix(int i) { itoa(i, a, 2); return a; } int main() { int len, n; int count = 0; cin >> len; n = pow(2, len); for(int i = 0; i

【本文地址】

杂题

杂题

今日新闻

推荐新闻