算法学习之路|牢房问题

简介: 在监狱里有n间牢房,一开始每个牢房门都是关着的,每间房里有一个囚犯。监狱长每次先喝一杯威士忌,然后下去打开或关闭一部分牢房的门。第一次把每扇门都打开,第二次改变第2,4,6…扇门的状态,第三次改变第3,6,9,…扇门的状态,以此类推,持续n轮。 给出牢房的数量,求多少囚犯可以逃走。

在监狱里有n间牢房,一开始每个牢房门都是关着的,每间房里有一个囚犯。监狱长每次先喝一杯威士忌,然后下去打开或关闭一部分牢房的门。第一次把每扇门都打开,第二次改变第2,4,6…扇门的状态,第三次改变第3,6,9,…扇门的状态,以此类推,持续n轮。
给出牢房的数量,求多少囚犯可以逃走。
输入格式
输入有多组数据,第一行一个数t,表示t组数据,接下来t行,每行一个数n

输出格式
每组数据,打印一个数,表示能逃走的人数量
输入样例:
2
5
100
输出样例:

2
10

本题是模拟题,代码也是模拟的思路,不过可以总结规律,用数论思想,推出最终结果一定是完全平方数的个数。(n开根号即可)

#include<stdio.h>
int main()
{
    int x,n,i,j,k,num=0;
    int a[200],b[200];
    scanf("%d",&x);
    for(i=0;i<x;i++)
    {
        scanf("%d",&n);
        for(j=0;j<n;j++)
        {
            a[j]=1;
        }
        for(k=2;k<=n;k++)
        {
            for(j=1;j<=n;j++)
            {
                if(j%k==0)
                    a[j-1]=-a[j-1];
            }
        }
        for(j=0;j<n;j++)
        {
            if(a[j]==1)
            {
            num++;
            }
        }
            b[i]=num;
            num=0;
    }
    for(i=0;i<x;i++)
    {
        printf("%d\n",b[i]);
    }
    return 0;
}
目录
相关文章
|
3月前
|
机器学习/深度学习 数据采集 搜索推荐
Paper Digest | 突破个性化推荐数据稀疏性:长尾增强的图对比学习算法研究
本文提出了一种新的长尾增强的图对比学习方法(LAGCL),该方法促使模型同时兼顾头部节点与尾部节点之间的知识,并通过长尾增强技术来使模型产出更均匀更准确的节点表征,从而改进基于 GNN 的推荐任务。
|
3月前
|
算法 网络协议 Linux
【Cisco Packet Tracer】交换机的自学习算法
【Cisco Packet Tracer】交换机的自学习算法
60 0
|
4月前
|
机器学习/深度学习 算法
机器学习 - [集成学习]Bagging算法的编程实现
机器学习 - [集成学习]Bagging算法的编程实现
39 1
|
2天前
|
机器学习/深度学习 算法
应用规则学习算法识别有毒的蘑菇
应用规则学习算法识别有毒的蘑菇
|
13天前
|
机器学习/深度学习 算法 数据挖掘
【Python机器学习专栏】关联规则学习:Apriori算法详解
【4月更文挑战第30天】Apriori算法是一种用于关联规则学习的经典算法,尤其适用于购物篮分析,以发现商品间的购买关联。该算法基于支持度和置信度指标,通过迭代生成频繁项集并提取满足阈值的规则。Python中可借助mlxtend库实现Apriori,例如处理购物篮数据,设置支持度和置信度阈值,找出相关规则。
|
13天前
|
机器学习/深度学习 算法 前端开发
【Python机器学习专栏】集成学习算法的原理与应用
【4月更文挑战第30天】集成学习通过组合多个基学习器提升预测准确性,广泛应用于分类、回归等问题。主要步骤包括生成基学习器、训练和结合预测结果。算法类型有Bagging(如随机森林)、Boosting(如AdaBoost)和Stacking。Python中可使用scikit-learn实现,如示例代码展示的随机森林分类。集成学习能降低模型方差,缓解过拟合,提高预测性能。
|
26天前
|
机器学习/深度学习 算法 前端开发
Scikit-learn进阶:探索集成学习算法
【4月更文挑战第17天】本文介绍了Scikit-learn中的集成学习算法,包括Bagging(如RandomForest)、Boosting(AdaBoost、GradientBoosting)和Stacking。通过结合多个学习器,集成学习能提高模型性能,减少偏差和方差。文中展示了如何使用Scikit-learn实现这些算法,并提供示例代码,帮助读者理解和应用集成学习提升模型预测准确性。
|
27天前
|
机器学习/深度学习 算法 Python
使用Python实现集成学习算法:Bagging与Boosting
使用Python实现集成学习算法:Bagging与Boosting
22 0
|
28天前
|
算法 安全 数据可视化
python关联规则学习:FP-Growth算法对药品进行“菜篮子”分析
python关联规则学习:FP-Growth算法对药品进行“菜篮子”分析
|
1月前
|
算法
【算法学习--字符串】(不含KMP算法)
【算法学习--字符串】(不含KMP算法)