西北工业大学C程序设计基础NOJ T024

本题来自UVA 580 危险的组合 Critical Mass

题目描述

有一些装有铀(用U表示)和铅(用L表示)的盒子,数量均足够多。要求把n个盒子放成一行,但至少有3个U放在一起,有多少种方法?

输入描述 Input Description

包含一个整数n

输出描述 Output Description

输出一个整数表示方法数。

样例输入 Sample Input

样例1:4
样例2:5

样例输出 Sample Output

样例1:3
样例2:8

数据范围及提示 Data Size & Hint

对于100%的数据(3<=N<=30)


题解

思路

本题是一个数学问题,需要进行分类讨论。

题目让我们求存在连续3个以上铀(危险组合)的个数有几个,假设把n个盒子放成一行,有$cnt \left ( n \right ) $种方法,可分两方面来考虑:

  1. 如果把第一个盒子拿掉,剩下的n-1个盒子满足条件有$cnt \left ( n-1 \right ) $种方法,第一个盒子可放铀或铅,因此这种情况共有 $2*cnt \left ( n-1 \right ) $种方法。
  2. 如果把第1个盒子拿掉,剩下的n-1个盒子不满足条件,那么只有第一至三个盒子是铀,第四个盒子是铅才可以。(第四个盒子如果是铀,那么234盒子就满足条件了。)此后的n-4个盒子共有$2^{n-4}$种情况,需要减去满足条件的$cnt \left ( n-4 \right ) $种方法。

故$cnt \left ( n \right )=2*cnt \left(n-1\right)+2^{n-4}-cnt\left(n-4\right) $。

以上讨论在n>4的条件下成立,其他情况需要单独讨论。

源代码

//NOJ T024
//20221024 by Lozumi
#include <stdio.h>
#include <math.h>

int cnt(int n);
int main(){
    int n;
    scanf("%d",&n);
    printf("%d\n",cnt(n));
    return 0;
}

int cnt(int n){
    if(n<3) 
    return 0;
    else if(n==3) 
    return 1;
    else if(n==4) 
    return 3;
    else
        return 2*cnt(n-1)+pow(2,n-4)-cnt(n-4);
}

参考资料

UVA 580 危险的组合 Critical Mass_cq_zry的博客-CSDN博客

=EOF=

Last modification:November 21, 2022
如果觉得我的文章对你有用,请随意赞赏~