这个作业是完成离散数学相关的计算题
CSE 21 HW 2
(1)(a)至少可以除以多少个三位数的正整数
6或7?
(b)[3000]中有多少个整数= {1,2,3,…。 。 。 ,2999、3000}不能被2、3或7整除吗?
(c)我们可以用多少种方式列出数字{1、1、2、2、3、4、5},所以没有
两个相同的数字在连续的位置?
(2)在每种情况下,都要编写一个递归关系,包括基本案例,
描述问题的递归结构。简要说明如何
您获得了复发。您不需要解决封闭形式
式。
(a)令C(n)为n×n网格中1×1像元的数量。写一个
C(n)的重复发生。
(b)一堆摩托车和汽车要在一条街道上平行停放。的
街道可以容纳n辆摩托车,但汽车会占用三个摩托车空间。
设A(n)为一个汽车上摩托车的布置数量
适合n辆摩托车的街道。例如,A(5)= 4,因为
在具有五个摩托车位的街道上停放车辆的四种方式。如果M
C代表摩托车,C代表汽车,则这四种安排
是:MMC,MCM,CMM和MMMMM。为A(n)写一个递归。
(c)令B(n)为长度n的二进制字符串的数目,其中没有三个
连续0。为B(n)写一个递归。
(d)任何二进制字符串都可以分成相同的连续块
角色,称为跑步。例如,001110100000具有:
•长度为2的0s
•长度为3的1s
•长度为1的0的游程
•长度为1的1s
•长度为5的0s
Let B(n) be the number of length n binary strings where each run of
1s has even length. Find a recurrence for B(n).
(e) Let S(n) be the number of subsets of {1, 2, . . . , n} having the following
property: no two elements in the subset are consecutive integers. The
empty set with no elements should be included in your count. Write
a recurrence for S(n).
(f) A ternary string is like a binary string except it uses three symbols, 0,
1, and 2. For example, 12210021 is a ternary string of length 8. Let
T(n) be the number of ternary strings of length n with the property
that there is never a 2 appearing anywhere after a 0. For example,
12120110 has this property but 10120012 does not. Write a recurrence
for T(n).
Note: For parts (g) and (h) of this problem, to “tile a rectangle” is to
cover it with tiles so that no tiles overlap, no tiles are hanging off the
edge of the rectangle, and every space on the rectangle is covered by
some tile.