`

[转]芯片测试题型

阅读更多
有n个人,其中超过半数是好人,剩下的是坏人
好人只说真话,坏人可能说真话也可能说假话
这n个人互相都知道对方是好人还是坏人
现在要你从这n个人当中找出一个好人来,只能通过以下方式:
每次挑出两个人,让这两个人互相说出对方的身份,
你根具两个人的话进行判断。
问通过何种方法才能最快的找出一个好人来,
(要考虑最坏的情况)

算法分析:
(1)好人+好人---好人,好人
(2)好人+坏人---好人,坏人 或 坏人,坏人
(3)坏人+坏人---好人,好人 或 坏人,坏人 或 坏人,好人
如果两人说法相同(并且都是好人),则保留一人。如果两人说法不同或同说是坏人,则两人全部去除。这样可以保证:
(1)子问题至少减到1/2.
(2 ) 仍能保证剩余人群中好人占多数。这是因为原人群超半数是好人,将原人群分为(1)(2)(3)后,因为(2)中好人比例是1/2,且将全部被淘汰,故(1)(3)之和中好人比例不会比原人群低,即大于1/2。而对(1)(3)的处理时,好人会两中取一,坏人要么两中取一,要么全部被放弃。
因此,T(n)=T(n/2)+O(n)   线性时间。
分享到:
评论

相关推荐

    EDA 期末复习资料 以及考试题型

    EDA 期末复习资料及考试题型 EDA(Electronic Design Automation,电子设计自动化)是指使用计算机辅助设计(Computer-Aided Design,CAD)和计算机辅助工程(Computer-Aided Engineering,CAE)技术来设计、开发和...

    电赛-数字拨盘(旋转编码器).rar

    电赛-数字拨盘(旋转编码器)。数字拨盘的实现通常需要使用旋转编码器...总之,数字拨盘是EDC竞赛中常见的一种题型,需要参赛者具备电子、电气类专业的知识和技能,通过综合考虑硬件、软件、精度和稳定性等方面来实现。

    四川省射洪市2021届高三下学期5月高考考前模拟测试理科综合试题 Word版含答案.doc

    1. 高考模拟测试:这是针对即将参加高考的学生进行的一次模拟考试,目的是让学生熟悉高考的流程和题型,以便更好地准备正式考试。 2. 理科综合能力测试:理科综合能力测试通常包括物理、化学、生物等理科科目,旨在...

    最新嵌入式系统课程考试题型和答案.docx

    嵌入式系统课程考试题型和答案 嵌入式系统是一种以应用为中心、以计算机技术为基础、软硬件可裁剪、能满足应用系统对功能、可靠性、成本、体积、功耗等指标的严格要求的专用计算机系统。它具有多种类型的处理器和...

    嵌入式系统课程考试题型和答案.doc

    《嵌入式系统课程考试题型与答案解析》 嵌入式系统是计算机科学的一个重要分支,它主要涉及以应用为中心、以计算机技术为基础的专用计算机系统。这些系统具有高度可裁剪的软硬件特性,能够满足特定应用在功能、可靠...

    FPGA期末复习题(答案)知识点题型.docx

    CLB用于实现复杂的逻辑功能,I/O模块处理芯片内外部的信号交互,而内部连线则负责连接各个功能单元。 2. CPLD与FPGA的区别: CPLD(Complex Programmable Logic Device)的内部连线是连续式的,延迟固定,适合简单...

    嵌入式系统课程考试题型和答案.docx

    ### 嵌入式系统课程考试题型和答案解析 #### 1. 什么是嵌入式系统?嵌入式系统的特点是什么? **嵌入式系统定义:** 嵌入式系统是一种特殊的计算机系统,它以应用为中心,以计算机技术为基础,并且能够根据应用...

    2022年嵌入式系统课程考试题型和答案.docx

    硬件调试常用的方法有直接测试法、ROM监控器、ROM仿真器、在线仿真器(ICE)以及片上调试(OCD),如JTAG、BDM和基于主机的调试等技术。软件调试则包括非交叉调试,如使用模拟器在宿主机上进行虚拟目标机环境的调试...

    嵌入式系统课程考试题型和答案.pdf

    开发嵌入式系统通常采用的编程语言有C语言(用于操作系统和硬件相关程序)、C++(大型应用程序)、汇编语言(底层硬件接口和算法)、VHDL(CPLD/FPGA芯片逻辑)以及Java(JSP开发和大型应用)。 嵌入式系统与专用...

    嵌入式系统课程考试题型和答案借鉴.pdf

    开发嵌入式系统常用的语言有C语言(用于操作系统和硬件相关程序),C++(大型应用程序),汇编语言(底层硬件接口和算法模块),C#(大型应用程序),VHDL(CPLD/FPGA芯片逻辑设计),以及JAVA(JSP开发和大型应用)...

    中级网络工程师历年真题详解

    要构成这样的内存,需要知道每片存储芯片的容量,从而计算出需要多少片芯片。这里用的是32K×8bit的存储芯片,意味着每片芯片可以存储32KB数据。所以,160KB的内存需要5片这样的芯片。 2. 中断响应时间: - 中断...

    第十二届蓝桥杯单片机模拟测试客观题程序设计题

    单片机,又称为微控制器,是将CPU、内存、定时器/计数器、输入/输出接口等集成在一个芯片上的微型计算机。它们广泛应用于各类嵌入式系统,如家电控制、汽车电子、工业自动化等领域。了解单片机需要掌握以下几个关键...

    江苏省二级C++考试真题

    江苏省二级C++考试真题是针对非计算机专业学生的计算机基础知识和应用能力的等级考试,主要测试考生对C++编程语言的掌握以及计算机基础理论的理解。试卷由计算机基础知识部分和程序设计部分组成,总分60分,考试时间...

Global site tag (gtag.js) - Google Analytics