装错信封问题c语言,装错信封问题c语言怎么办

发布时间:2023-01-07

本文目录一览:

1、用C++数组解
2、组合问题
3、c语言问题 伯努利装错信封问题
4、初中递归题
5、c语言题,n封信装入n个对应信封。问,全部装错的情况有几种。请用for和递归两种方法解决。
6、C语言编程题这题咋做啊

用C++数组解

由于已经给出递推公式,那这个代码的实现其实很简单,如以下代码

int D[11];
D[1] = 0;
D[2] = 1;
for (int i = 3; i <= 10; ++i) {
    D[i] = (i - 1) * (D[i - 1] + D[i - 2]);
}

定义一个数组,初始化前两位,然后再根据公式迭代计算

组合问题

这个是装错信封类的变题 为方便,我们先把n个不同的元素及相应的位置都编上序号1,2,…,n,并且约定:在n个不同元素的排列中 1° 若编号为i(i=1,2,…,n)的元素排在第i个位置,则称元素i在原位;否则称元素i不在原位。 2° 若所有的元素都不在原位,则称这种排列为n个不同元素的一个错排(若每个元素都在原位则称为序排)。 按照上面约定,“装错信封问题”即为n个不同元素的错排问题,则可构建“装错信封问题”的数学模型为: 在n个不同元素的全排列中,有多少种不同的错排?

模型求解

应用集合中的容斥原理,我们就可得到“装错信封问题”的数学模型的求解公式。 设I表示n个不同元素的全排列的集合
Ai(i=1,2,…,n)为元素i在原位的排列的集合
Ai∩Aj(1≤i<j≤n)为元素i与j在原位的排列的集合
A1∩A2∩…∩An为n个元素的序排的集合
则它们的排列数分别为:

  • |I| = n!
  • |Ai| = (n-1)!
  • |Ai∩Aj| = (n-2)!
  • ...
  • |A1∩A2∩…∩An| = (n-n)! = 0! 根据容斥原理即得“装错信封问题”的数学模型的求解公式(即n个不同元素的错排数)为:
f(n) = n![1 - 1/1! + 1/2! - 1/3! + … + (-1)^n * 1/n!]

例如:f(5) = 44,有44种错放法。

c语言问题 伯努利装错信封问题

全排列的筛选

#include <stdio.h>
#include <stdlib.h>
int printed;
void draw(int* a, int k) {
    int i;
    for(i = 0; i < k; i++) {
        printf("%d", a[i]);
    }
    printf("\n");
}
void Settle(int *a, int iStep, int k) {
    int i;
    for(i = 0; i < iStep - 1; i++) {
        if(a[iStep - 1] == a[i]) return;
    }
    if(iStep == k) {
        draw(a, k);
        printed++;
    }
    for(i = 1; i <= k; i++) {
        if(i == iStep + 1) continue;
        a[iStep] = i;
        Settle(a, iStep + 1, k);
    }
}
void main() {
    int* a;
    int k;
    scanf("%d", &k);
    a = (int*)calloc(k, sizeof(int));
    Settle(a, 0, k);
    printf("s=%d\n", printed);
}

初中递归题

  1. 一只母兔从四岁开始每年生一只小母兔,按此规律,第N年时有多少只母兔?
  2. 楼梯有N阶,上楼可以一步上一阶,也可以一次上二阶。编一个程序,计算共有多少种不同的走法。
  3. 某人写了n封信和n个信封,如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。
  4. 有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半,仍觉得不过瘾又多吃了一个,以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候,看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子。
  5. 写一个计算斐波那挈数列的递归函数(即后面一项为前两项之和)。
  6. Hanoi问题:设有三个塔座,依次命名为x,y,z。有n个直径不同的圆盘,由小到大依次编号为1、2、……,n。开始时,它们全部按递减的次序插在塔座上。现要求按下列规则把n个圆盘按次序插放在z塔座上。
    • (1)每次只能移动一个圆盘;
    • (2)圆盘可以从任一个塔座上移到另一个塔座上;
    • (3)任何时刻都不能把一个较大的圆盘压在较小的圆盘上。
  7. 把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
  8. 有一栋楼房,假设有100层,我从第100层往下拣钱,每一层的钱等于楼层数 × 10。例第1层是 1×10 = 10块钱,求100层我共拣到多少钱?
  9. 有一栋楼房,假设有10层。每一次的钱等于,我从第10层往下拣,当前层的钱 = 以前层累加的钱 × 当前层数-1。问10层楼我共拣多少钱?[可以假设第1层是7块钱]

c语言题,n封信装入n个对应信封。问,全部装错的情况有几种。请用for和递归两种方法解决。

#include "stdio.h"
int ans = 0, n;
bool visit[30];
void dfs(int cur) {
    if (cur == n) {
        ++ans;
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (i == cur || visit[i])
            continue;
        visit[i] = true;
        dfs(cur + 1);
        visit[i] = false;
    }
}
main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        visit[i] = false;
    for (int i = 1; i < n; ++i) {
        visit[i] = true;
        dfs(1);
        visit[i] = false;
    }
    printf("%d\n", ans);
}

n不能太大,不然会运行很久的。

C语言编程题这题咋做啊

分析,假如有N封信和N个信封:

  • 第一步:第一封信,错误信封情况:N-1个
  • 第二步:假设与第一封信装错的信封为第A个信封,则此步就找第A个信封,与之匹配会出错的信封有N-1个
  • 第三步(如果N大于2):与第M封信匹配错误的信封情况为N-2(M≠1,M≠A)
  • 第四步:假设与第M封信装错的信封为第B个信封,则此步就找第B个信封,与之匹配会出错的信封有N-2个 依次类推,算法就是:
(N-1) × (N-1) × (N-2) × (N-2) × … × 1 × 1

自己想出来的,应该是对的,楼主自己测试看看,应该没错,代码就不写了,很简单的循环。