精华内容
下载资源
问答
  • 数据流中的中位数

    千次阅读 2018-07-02 11:28:58
    题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。由于...

    题目描述

            如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

    由于数据是从一个数据流中读出来,因而数据的数目随着时间的增加而增加,如果用一个数据容器来保存从流中读出来的数据,则当新的数据从流中读出来的时候,这些数据就插入数据容器。这个数据用什么数据结构定义合适呢?接下来讨论一下最合适的数据结构:

    首先,先用一个表格列出可用数据结构的各复杂度

     

    不同数据结构的时间复杂度
    数据结构 插入的时间复杂度 得到中位数的时间复杂度
    没有排序的数组 O(1) O(n)
    排序的数组 O(n) O(1)
    排序的链表 O(n) O(1)
    二叉搜索树 平均O(logN),最差O(n) 平均O(logN),最差O(n)
    VAL树 O(logN) O(1)
    最大堆和最小堆 O(logN) O(1)

    接下来,细细分析一下:

     

    1. 数组是最简单的数据容器。如果数组没有排序,那么可以用前面提到的Partition函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度分别是O(1)和O(n)。
    2. 在往数组里插入数字的时候我们可以让数组保持排序。这时由于可能需要移动O(n)个数字,因此需要O(n)的时间复杂度。在已排好的数组中取中位数,我们只需要O(1)的时间复杂度即可。
    3. 排序的链表是另外一种选择,我们需要O(n)的时间复杂度才能在链表中找到其合适的位置插入新的数据。如果定义两个指针指向链表中间的节点,那么可以在O(1)的时间内得出中位数。
    4. 二叉搜索树可以把插入新数据的平均时间复杂度降低到最低,但是由于二叉搜索树极度不平衡,从而看起来像一个排序的链表的时候,插入新数据的时间仍然是O(n),为了得到中位数,可以在二叉树节点中添加一个表示子树节点数目的字段。有了这个字段,可以在平均O(logN)时间内得到中位数,但最差情况仍然是O(logN)。
    5. 为了避免二叉搜索树的最差情况,可以利用平衡的二叉搜索树,即VAL树。通常VAL树的平衡因子是左右子树的高度差。可以稍作修改,把VAL树的平衡因子改为左右子树节点数目之差。有了这个改动,可以用O(logN)时间往VAL树中添加一个新节点,同时用O(1)时间得到所有节点的中位数。
    6. 虽然VAL树的效率很高,但是大部分编程语言的函数库是没有实现这个数据结构的,在面试期间短短几十分钟也是不可能实现这个功能的,所以只能考虑其他办法。

     

    从上图可以看到,如果容器中数据的数目是奇数,那么两个指针指向同一个数据。

    我们可以发现,整个数据容器被分成两个部分。位于容器左边部分的数据结构比右边的数据结构小。另外,p1指针指向的数据是左边部分最大的数,p2指向的是右边部分最小的数。

     

            OK,找出最优的数据结构后,我们再考虑一点细节。首先要保证数据平均分配到两个堆中,因此两个堆中的数据的数目之差不能为1。为了实现平均分配,可以在数据的总数目是偶数的情况下把新数据插入最小堆,否则插入最大堆。

            还要保证最大堆的所有数都大于最小堆,因此按照前面的分配规则,会把新的数据插入最小堆。如果此时插入最小堆的数据大于最大堆的最小值,那么它就不能成为最小堆的数据,因此我们需要把这个新数据先插入最大堆,然后取出最大堆里最小值min,再把找到min插入最小堆中,以此来满足我们的规则——最小堆中所有数字都小于最大堆的数字。同理可插入新数据进入最大堆。

    以下为C#实现的代码,用两个list作为堆容器来实现的:

    
    using System;
    using System.Collections.Generic;
    
    namespace 数据流中的中位数
    {
        class Program
        {
            static void Main(string[] args)
            {
                int[] num = new int[9] { 5, 2, 3, 4, 1, 6, 7, 0, 8 };
                Solution s = new Solution();
                for (int i = 0; i < num.Length; i++)        //模拟逐次从流中读出数据,取其中位数查看结果
                {
                    s.Insert(num[i]);
                    Console.WriteLine(s.GetMedian());
                }
            }
        }
        class Solution
        {
            private List<int> max = new List<int>();                //容器右边较大数所存储的堆
            private List<int> min = new List<int>();                //容器左边较小数所存储的堆
    
    
            /// <summary>
            /// 首先需要保证最大堆和最小堆能够平均分配数据,因此两个堆的数目差不能超过1.为了实现平均分配,可以在数据的总数目是偶数时把新数据插入最小堆,否则插入最大堆。
            /// </summary>
            /// <param name="num">插入的数字</param>
            public void Insert(int num)
            {
                //如果两个容器数量不平衡,则让其保持平衡,把新数据添加到max中
                if (((min.Count + max.Count) & 1) == 0)
                {
                    //新插入的数据大于最小堆的最大值,那么先把这个数据添加进最大堆,然后取出最大堆的最小值,把最小值插入最小堆min中
                    if (max.Count > 0 && num > max[0])
                    {
                        Add(max, num);
                        num = max[0];
                        max.RemoveAt(0);
                    }
                    Add(min, num);
                }
                else
                {
                    //如果要把新数据插入最大堆max,先判断新数据是否小于最小堆的最大值,如果是,那么先把新数据插入最小堆,取出最小堆的最大值,
                    //把得到的最大值插入最大堆max中
                    if (min.Count > 0 && min[min.Count - 1] > num)
                    {
                        Add(min, num);
                        num = min[min.Count - 1];
                        min.RemoveAt(min.Count - 1);
                    }
                    Add(max, num);
                }
            }
    
    
            /// <summary>
            /// 用来得到中位数,如果最大堆和最小堆的数量加起来是偶数,说明中位数得计算,那么求最大堆最小值与最小堆最大值的和的一半即可
            /// </summary>
            /// <returns>中位数</returns>
            public double GetMedian()
            {
                int size = min.Count + max.Count;
                //如果两个堆数据数目之和为奇数,说明返回最小堆的最大值即可(因为优先插入最小堆,最小堆会比最大堆多一个数)
                if ((size & 1) == 0)
                    return (double)(min[min.Count - 1] + max[0]) / 2.0;
    
    
                return (double)min[min.Count - 1];
            }
    
    
            //排好序的添加到两个堆中,都按升序排列,在调用最小堆时,则逆序调用即可
            private void Add(List<int> list, int num)
            {
                if (list.Count == 0)
                    list.Add(num);
                else
                {
                    for (int i = 0; i < list.Count; i++)
                    {
                        if (list[i] > num)
                        {
                            list.Insert(i, num);
                            return;
                        }
                    }
                    list.Add(num);
                }
            }
        }
    }

     

    展开全文
  • 数字电子钟的设计与制作

    万次阅读 多人点赞 2018-04-14 09:35:28
    方案一:时钟的显示可以用多位七段 LED 数码管显示,七段  LED 数码管显示耗能多,而且显示位数有限,每增加一位都要在程序设计和硬件设计方面增加很多的工作量,不利于电路的扩展,而且无法显示年、月、日、星期...

    学号

    姓名

    实物演示(60%)

    论文成绩(30%)

    平时成绩(10%)

    总成绩

    0144300

     

     

     

     

     

    0144297

     

     

     

     

     

     

    评语:该小组基于单片机设计了一个系统,主要实现了数字时钟实时显示和远程通信的功能,硬件和软件系统工作正常,达到了设计要求。报告内容充实,格式正确,程序代码注解清晰,程序流程正确。

                                                       指导教师:

                                                                 年     月     日

     

     

     

     

     

     

     

     

    设计题目:数字电子钟的设计与制作

     

     

     

     

     

     

     

     

     

     

     

     

    组员姓名:

    班级:1

     

     

    年 月 日

     

     

    摘要:单片机模块中最常见的是数字钟,数字钟是一种用数字电路技术实现时、分、秒计时的装置,与机械式时钟相比具有更高的准确性和直观性,且无机械装置,具有更更长的使用寿命,因此得到了广泛的使用。这正符合了现代时钟的设计要求。数字钟是采用数字电路实现对.时,分,秒.数字显示的计时装置,广泛用于个人家庭,车站, 码头办公室等公共场所,成为人们日常生活中不可少的必需品,由于数字集成电路的发展和石英晶体振荡器的广泛应用,使得数字钟的精度,远远超过老式钟表, 钟表的数字化给人们生产生活带来了极大的方便,而且大大地扩展了钟表原先的报时功能。诸如定时自动报警、按时自动打铃、时间程序自动控制、定时广播、自动起闭路灯、定时开关烘箱、通断动力设备、甚至各种定时电气的自动启用等,所有这些,都是以钟表数字化为基础的。因此,研究数字时钟及扩大其应用,有着非常现实的意义。因此本论文所做的数字时钟采用了以单片机(STC89C51)为核心,结合相关的外围元器件例如液晶显示、按键电路、复位电路、闹钟电路,再配以相应的软件,达到制作简易数字钟的目的,能实现实时时钟显示的功能,能进行年、月、日、时、分、秒和实时温度的显示,并且通过蓝牙模块实现两台单片机的通信功能。

    关键词:单片机,数字钟,蓝牙模块

     

     

     

     

     

     

     

     

     

     

    Abstract: The most common one is the digital clock, the digital clock is a digital circuit technology to achieve hours, minutes and seconds of the device, compared with the mechanical clock has a higher accuracy and intuitive, and no mechanical Device, has a longer life, so get a wide range of use. This is in line with modern clock design requirements. Digital clock is the use of digital circuits to achieve. Hours, minutes, seconds. Digital display of the timing device, widely used in personal homes, stations, terminals and other public places office, become essential necessities of daily life, digital integrated circuits Development and extensive application of quartz crystal oscillator, making the digital clock accuracy, far more than the old-fashioned watches, watches and clocks to the digital production and life has brought great convenience, but also greatly extended the timekeeping function of the original watch. Such as automatic timer alarm, automatic bell on time, time program automatic control, time broadcast, automatic starting and closing lights, timer switch oven, off power equipment, and even a variety of automatic electrical timing enabled, all of these are digital clocks based on. Therefore, the study of digital clock and expand its application, has a very practical significance. Therefore, the digital clock used in this thesis adopts the microcontroller (STC89C51) as the core, combined with the related peripheral components such as liquid crystal display, button circuit, reset circuit, alarm circuit, matched with the corresponding software to achieve the production of simple digital clock Time, minutes, seconds and real-time temperature display, and through the Bluetooth module to achieve the communication functions of the two single-chip microcomputer, can achieve the function of real-time clock display, can carry out year, month,

    Keywords: MCU, digital clock, Bluetooth module

    目录

     

     

    1. 设计任务与要求 3

    1.1 设计任务 3

    1.2 设计要求 3

    1.2.1  基本要求 3

    1.2.2  发挥部分 3

    2. 方案论证与选择 3

    2.1 主控芯片选择 3

    2.2 温度传感器模块选择 3

    2.3 时钟显示模块选择 3

    2.4 显示模块选择 3

    3. 硬件电路设计 3

    3.1 工作原理 3

    3.2 元器件及其引脚原理 3

    3.3 单元模块电路 3

    4. 系统软件设计 3

    4.1系统主程序及流程图 3

    4.2 DS1302时钟芯片的读操作流程图 3

    4.3液晶模块的写操作流程图 3

    4.4按键调整模块流程图 3

    4.5通信模块流程图 3

    5. 系统测试 3

    5.1测试仪器 3

    5.2测试方法 3

    5.2.1 硬件测试 3

    5.2.2 软件测试 3

    5.3 测试结果 3

    6. 设计总结 3

    6.1 本文的主要工作和成果 3

    6.2 设计中不足及其展望 3

    参考文献 3

    附录一 电路图 3

    附录二 程序代码 3

     

    1. 设计任务与要求

    在本次课题中设计了一个单片机与时钟芯片相结合的电路,实现实时显示时间,并能够进行远程通信。初步确定设计系统由主控模块、时钟模块、显示模块、键扫描电路模块,温度显示模块共5个模块组成。设计采AT89C51系列单片机,以KeilC51语言为程序设计的基础,设计出用液晶显示年、月、日、周、时、分、秒的时钟,并且能够显示温度,当温度超过一定范围后蜂鸣器报警。

    1.1 设计任务

    设计一个可调时及日期显示的数字电子时钟。

    1.2 设计要求

        设计一个数字电子时钟,要求其能够显示日期,时分秒,以及星期等信息;在实时时钟显示的基础上增加按键功能,要求其能够通过按键来调整时间,并且通过复位储存调整之后的时间;增加蓝牙模块,利用两个单片机开发板,通过蓝牙将上述功能由一个单片机发出,并由另一个单片机实现接收。

    1.2.1  基本要求

    1)数字钟具有显示时、分、秒的功能;由LEDLCD显示时间:时、分、秒;

    2)具有校时和校分的功能;

    1.2.2  发挥部分

    (1)具备报警功能:温度超过预警值后蜂鸣器报警;

    (2)其他功能:如在按键时会发出提示音、无线数据传输、远程控制等其他功能。

    2. 方案论证与选择

    2.1 主控芯片选择

    方案一:ATmega16 ATMEL 公司推出的一款基于AVR RISC 构架的低功耗CMOS 8 位单片机。ATmega16 16MHz 时有16MIPS 的运算速度,具有两周期硬件乘法器,从而使得设计人员可以在功耗和执行速度之间取得平衡, 且非易失性程序和数据存储器资源较大能满足程序代码设计需要。外设资源丰富:2 个具有独立预分频器和比较器功能的8 位定时/计数器;一个独立预分频器和比较/捕捉功能的16 位定时/计数器;支持4 PWM 输出、8 10 ADC。支持TWI 接口、USARTSPI 接口多机通信满足扩展功能的需要。

    方案二:AT89C51是一种带4K字节FLASH存储器FPEROM—Flash Programmable and Erasable Read Only Memory)的低电压、高性能CMOS 8微处理器,俗称单片机AT89C2051是一种带2K字节闪存可编程可擦除只读存储器的单片机。单片机的可擦除只读存储器可以反复擦除1000次。该器件采用ATMEL高密度非易失存储器制造技术制造,与工业标准的MCS-51指令集和输出管脚相兼容。由于将多功能8CPU和闪速存储器组合在单个芯片中,ATMELAT89C51是一种高效微控制器,AT89C051是它的一种精简版本。AT89C51单片机为很多嵌入式控制系统提供了一种灵活性高且价廉的方案。

    在本次实验中,选择了单片机开发板自带的AT89C51芯片。

    2.2 温度传感器模块选择

    本次设计中选用了DS18B20数字温度传感器,因为它接线方便,封装成后可应用于多种场合,如管道式,螺纹式,磁铁吸附式,不锈钢封装式,型号多种多样,有LTM8877LTM8874等等。主要根据应用场合的不同而改变其外观。封装后的DS18B20可用于电缆沟测温,高炉水循环测温,锅炉测温,机房测温,农业大棚测温,洁净室测温,弹药库测温等各种非极限温度场合。耐磨耐碰,体积小,使用方便,封装形式多样,适用于各种狭小空间设备数字测温和控制领域。

    2.3 时钟显示模块选择

    方案一:采用实时时钟芯片

    现在市场上有许多实时时钟集成电路,如:DS1287DS2887ds1302等。这些实时时钟芯片具备年、月、日、时、分、秒计时功能和多点定时功能,计时数据的更新每秒自动进行一次,不需要程序干预。因此,在工业实时测控系统中多采用这这一类专用芯片来实现实时时钟功能。

    方案二:是用单片机内的可编程定时器。

    利用单片机内部的定时计数器进行中断定时,配合软件延时实现时分秒的计时。该方案节省硬件成本,但程序设计较复杂。

    时钟显示模块选择了用芯片DS1302,因为DS1302以串行方式与单片机进行数据传送,它能够向单片机提供秒、分、时、日、月、年、及星期等实时时间信息,并能够对闰年天数自动调整,日历有效至2100年。DSl302由双电源中较大者供电,使系统在没有主电源的情况下也能保持时钟的连续运行。同时具有引脚少、体积小、价格低等优点,因此选择得到广泛应用的DS1302

    2.4 显示模块选择

    方案一:时钟的显示可以用多位七段LED数码管显示,七段 LED数码管显示耗能多,而且显示位数有限,每增加一位都要在程序设计和硬件设计方面增加很多的工作量,不利于电路的扩展,而且无法显示年、月、日、星期这些汉字,使得显示不够直观,灵活。但是这种设计方案在显示位数比较少时性价比比较高,价格便宜。  

    方案二:采用LCD液晶显示器显示。而LCD液晶显示则耗能少,能够显示年、月、日、星期等汉字,在显示方面更加灵活,而且改变显示时只要改变软件设计就可以,不用改变硬件电路的设计,易于电路的功能扩展。电路的软件设计也很简单。另外,这种设计硬件更加简洁。采用LCD液晶显示方案的缺点是在显示位数比较少时,价格略显昂贵。

    显示方案选择了LCD液晶显示器显示,因为LCD液晶显示则耗能少,能够显示年、月、日、星期等汉字,比起七段LED数码管在显示方面更加灵活。

    3. 硬件电路设计

    3.1 工作原理

    此电子时钟可显示的时间范围为:2000年1月1日0点至2100年12月31日23时59分。此时钟在正常计时模式下具有自动调整每月的天数的变化,并用内接电池对时间保持。时间为24小时制。

    接通电源对时间进行调整,按定时设置键确定被修改位的值。用时钟芯片记忆当前时间并保持,待下次接通电源无须调整能正确显示当前时间。

    时、分调整: 

    当定时设置键选中要修改的位时,如分(分闪烁时),按此键可以使分的值从当前值开始加一,加至60时变为00(59过后即显示00,不显示60);而时则在加至24时变为00(23过后即显示0,不显示24);日在加至32时变为00(即31过后即显示0,不显示32);月在加至13时变为00(即12过后即显示0,不显示13);年在至2100时变为2000(即2099过后即显示2000,不显示2100)

    3.2 元器件及其引脚原理

    (1)DS1302

     

    图3.2.1 DS1302引脚图

    图3.2.1示出DS1302的引脚排列,其中Vcc1为后备电源,VCC2为主电源。在主电源关闭的情况下,也能保持时钟的连续运行。DS1302由Vcc1或Vcc2两者中的较大者供电。当Vcc2大于Vcc1+0.2V时,Vcc2给DS1302供电。当Vcc2小于Vcc1时,DS1302由Vcc1供电。X1和X2是振荡源,外接11.0592kHz晶振。RST是复位/片选线,通过把RST输入驱动置高电平来启动所有的数据传送。RST输入有两种功能RFBLN2012090A1T:首先,RST接通控制逻辑,允许地址/命令序列送入移位寄存器SMBJ70A-TR;其次,RST提供终止单字节或多字节数据的传送手段。当RST为高电平时,所有的数据传送被初始化,允许对DS1302进行操作。如果在传送过程中RST置为低电平,则会终止此次数据传送,I/O引脚变为高阻态。上电运行时,在Vcc≥2.5V之前,RST必须保持低电平。只有在SCLK为低电平时,才能将RST置为高电平。I/O为串行数据输入输出端(双向),后面有详细说明。SCLK始终是输入端。

    (2)DS18B20引脚图如图3.2.2所示。

     

    图3.2.2 DS18B02引脚图

    GND为电源地

    DQ为数字信号输入/输出端

    VDD为外接供电电源输入端(在寄生电源接线方式时接地)

    (3)LM016L

     

    图3.2.3 LM016L实物图

    第1脚:VSS为地电源。 

    第2脚:VDD接5V正电源。 

    第3脚:VL为液晶显示器对比度调整端,接正电源时对比度最弱,接地时对比度最高,对比度过高时会产生“鬼影”,使用时可以通过一个10K的电位器调整对比度。 

    第4脚:RS为寄存器选择,高电平时选择数据寄存器、低电平时选择指令寄存器。 

    第5脚:R/W为读写信号线,高电平时进行读操作,低电平时进行写操作。当RS和R/W共同为低电平时可以写入指令或者显示地址,当RS为低电平R/W为高电平时可以读忙信号,当RS为高电平R/W为低电平时可以写入数据。 

    第6脚:E端为使能端,当E端由高电平跳变成低电平时,液晶模块执行命令。 

    第7~14脚:D0~D7为8位双向数据线。 

    第15脚:背光源正极。 

    第16脚:背光源负极。

    LM016L液晶模块采用HD44780控制器,hd44780具有简单而功能较强的指令集,可以实现字符移动,闪烁等功能,LM016L与单片机MCU通讯可采用8位或4位并行传输两种方式,hd44780控制器由两个8位寄存器,指令寄存器(IR)和数据寄存器(DR)忙标志(BF),显示数RAM(DDRAM),字符发生器ROMA(CGOROM)字符发生器RAM(CGRAM),地址计数器RAM(AC)。IR用于寄存指令码,只能写入不能读出,DR用于寄存数据,数据由内部操作自动写入DDRAM和CGRAM,或者暂存从DDRAM和CGRAM读出的数据,BF为1时,液晶模块处于内部模式,不响应外部操作指令和接受数据,DDTAM用来存储显示的字符,能存储80个字符码, CGROM由8位字符码生成5*7点阵字符160中和5*10点阵字符32种.8位字符编码和字符的对应关系,可以查看参考文献(30)中的表4. CGRAM是为用户编写特殊字符留用的,它的容量仅64字节,可以自定义8个5*7点阵字符或者4个5*10点阵字符,AC可以存储DDRAM和CGRAM的地址,如果地址码随指令写入IR,则IR自动把地址码装入AC,同时选择DDRAM或CGRAM。

    (4)蓝牙模块

     

    图3.2.4 HC-05蓝牙模块

    32/31  LED 配对状态输出;配对成功输出高电平,未配对则输出低电平。 

    34     KEY 用于进入AT状态;高电平有效(悬空默认为低电平)。

    2      RXD 模块串口接收脚(TTL电平,不能直接接RS232电平!),可接单片机的TXD 

    1     TXD 模块串口发送脚(TTL电平,不能直接接RS232电平!),可接单片机的RXD 

    13    GND 地 

    12    VCC 电源(3.3V~5.0V)

    蓝牙模块AT常用指令:

    指令1:测试指令 

    指令 AT\r\n  

    应答 OK\r\n  

    指令2:设置/查询波特率 

    指令 AT+BAUD=<para1>\r\n  

    应答  OK 

    指令3:设置鉴权密码 

    指令  AT+PASSWORD=<para1>\r\n 

    应答 OK 

    指令4:设置/查询名称 

    指令 AT+NAME=<para1>\r\n  

    应答 OK

    指令5:设置主从

    指令AT+ROLE=M/S

    应答 OK

    3.3 单元模块电路

    1)独立按键模块

     

    图3.3.1 独立按键模块电路图

    根据设计要求,系统的按键电路用4x4矩阵式独立按键进行对时间的调整,按键就采用最简单的点动式按钮,由单片机的I/O进行扫描,来实现扫描按键功能。其中,时间调整按钮与单片机AT89C51的P10P11P12P13相连,其功能是按下set键开始进行时分调整,按hour进行时调整,按min进行分调整,按下OK确认调整开始调整时、分、秒,每按一次就改变一个相应的要改变的位;

    2)显示模块

     

    图3.3.2 显示模块电路图

    本系统显示中由LCD液晶显示器显示日期、时间、星期以及温度等的显示。

    显示模块电路,液晶模块的1管脚接电源地。2管脚接电源给液晶显示器供电,3管脚接电源用于提供液晶显示器显示驱动电压。4管脚接单片机的P2.6用于接收数据或者指令,5管脚接单片机的P2.5选择数据被读写到什么位置,6管脚接单片机的P2.7用于提供锁存信号。

    3)时钟芯片模块 

     

    图3.3.3 时钟芯片模块电路图

    DS1302时钟芯片是本系统实现高精度计时的关键。利用DS1302 时钟芯片独立于单片机来计时,在提高计时进度的同时也提高了整个系统的抗干扰能力。DS1302通过SCLKI/ORES端口和单片机AT89C51 进行通信。SCLK接至单片机P1.1口,在读写操作时给DS1302提供相应的时钟脉冲;I/O接至P1.2用来传送所有的数据;RES接至单片机P1.3上用来控制单片机与时钟芯片间的数据传送的开始与结束。

    4)主控模块

     

    图3.3.4 主控模块电路图

    主控模块的核心组成部分是单片机AT89C51, 承担着所有操作任务的调控与分派工作。

    (5)温度显示模块

     

    图3.3.5 温度显示模块电路图

    DS18B20数字温度传感器接线方便,耐磨耐碰,体积小,使用方便,封装形式多样,适用于各种狭小空间设备数字测温和控制领域。测温范围 -55℃~+125℃,固有测温误差(注意,不是分辨率,这里之前是错误的)1℃。

    (6)蜂鸣器设计模块

     

    图3.3.6 蜂鸣器设计模块电路图

    利用蜂鸣器模块实现温度的控制,当温度超过一定的范围时,蜂鸣器报警3级管一端连接10K的电阻并且连接P2.3,一端接蜂鸣器后连接电源,另一端接地。

    4. 系统软件设计

    软件是系统的主要组成部分,也是整个调试的重点和难点工作。本设计采用了Keil C51语言,因为C语言更接近机器语言,可以直接存取寄存器和I/O,编写的代码可以非常精确的被执行,可以编写出比一般编译系统高效的代码,可以作为不同语言或不同标准的接口。因此,依据课题设计的要求,采用C语言进行软件编程,用模块化程序设计思想,将软件划分成若干模块单元;包括:DS1302时钟显示模块、延时等模块,键盘扫描子程序,按键处理子程序模块,通信中断子程序。

    4.1系统主程序及流程图

    主程序的主要功能是显示日期时间信息。在主程序中,系统上电自动复位以后首先进行系统的液晶显示、时钟芯片DS1302初始化,然后读写日期、时间等信息,待数据读写结束后显示时钟。主程序流程如图4.1.1所示。

     

    图4.1.1系统主程序及流程图

    主程序说明,当主程序运行时,先将液晶显示器清屏,然后将单片机和时钟日历芯片DS1302初始化。

    4.2 DS1302时钟芯片的读操作流程图

    首先对时钟芯片DS1302初始化,经过对状态寄存器判断之后,对DS12887进行读操作,读操作时利用时钟日历地址相邻的特点,直接使地址增加,随后判断数据是否读完了。若读完了,则返回主程序;若没有读完,则继续增加地址,直到读数据完成为止。如图4.2.1所示。

     

    图4.2.1 DS1302时钟芯片的读操作流程图

    4.3液晶模块的写操作流程图

    本设计用的液晶模块是LCD液晶模块,这个模块可以进行串口通信也可以进行并口通信,由于单片机口线限制,在这里采用了串口设计思路。本设计采用了分屏显示的原理,在时间显示时显示屏一,在时间调整时显示屏二,其流程图分别如下图所示。

    图4.3.1 显示屏一

    在屏一显示流程图中,显示设置液晶显示设置为全屏显示,显示界面没有光标显示,年月日的显示从第二行第一个字符开始,时分秒的显示从第三行第一个字符开始。

     

    图4.3.2 显示屏二

    在显示屏二时应先判断是否有调整时间的请求,如果有时间调整的要求即有按键按下则显示此屏,显示此屏时先进行显示设置,因为要调整时间因此要用光标表示出要调整的位,因此显示设置中要调整出光标,调整时间时先调出当前时间,从当前时间开始调整,然后判断按键,根据按键来调整时间,调整完成之后再返回时间显示即显示屏一。

    4.4按键调整模块流程图

    按键调整程序模块是用来调整时间的,当SET按键按下时开始进行时钟调整,依次调整的参量为时、分、秒。当选择好了要调整的位后,再按OK键就会返回时间显示界面,从刚才调整好的时间开始显示、计时。其流程图如图4.4.1所示。

    图4.4.1按键调整模块流程图

    4.5通信模块流程图

    通信模块的协议包括两部分,一部分是主机程序,一部分是从机程序。这个子程序模块的作用是通过电脑来读写、调整单片机控制电路的时间。主机程序是在电脑上运行,然后将程序烧录在主机上,从远程控制时钟,可以对时钟的当前时间进行读写、调整操作。从机程序则是在单片机上运行,利用串口通信来接收自主机的操作指令,并且将时间传送给液晶显示屏。流程图如图4.5.1所示。

     

    图4.5.1通信模块流程图

    5. 系统测试

    5.1测试仪器

        在本次设计中,用到的测试仪器主要有Keil4,用来编写调试需要的程序;Protues7.0,用来做软件仿真以及软件调试;单片机开发板,主要用于调试keil文件编译生成的hex文件 ;温度传感器和蜂鸣器,用来测温并且在温度超过预警值后报警。

    5.2测试方法

    各程序模块具有一定的独立性,因此可以先调试模块,在模块功能都能实现的前提下,再调试总程序,这样能快捷地检查判断硬件或软件上的问题。

    5.2.1 硬件测试

    (1) 测试DS1302模块

    用STC ISP打开并下载HEX文件;默认下载后显示时分秒信息;按下set,进行时分秒设置,默认对分进行设置,按功能键调节值大小;按功能键的时、秒、确认键分进行值调节;再次按下ok退出设置;时钟依靠自身的晶振跑起来,显示时钟的时分秒;

    (2) 蓝牙通信模块测试

    利用串口助手中的AT 指令设置蓝牙的配对密码以及波特率,并且设置两个蓝牙分别为主从模块。

    将两个蓝牙分别接在两个单片机开发板上,蓝牙会不断闪烁,配对成功后蓝牙常亮。在配对成功的基础上,主机将发送的数据通过蓝牙传送,接收机通过蓝牙接收之后显示在液晶显示屏上,当两个单片机开发板上面的显示一致时,认为实现功能。

    (3) 测试蜂鸣器和温度模块

    将温度传感器插入,显示实时温度,当温度达到某一预警值时蜂鸣器报警,温度下降,蜂鸣器停止报警。

    (4) 测试按键模块

    利用按键模块对时钟进行调整,当按下设置键时,开始调整,然后分别对时分进行调整,当显示屏上的时分随着调整按键而开始相应地变化时,按键模块正常。

    5.2.2 软件测试

    这里用C语言编写程序,用keil作为设计程序的软件平台。

    1. 先打开keil软件

     

    图5.2.1

     2. 新建项目并保存

     

    图5.2.2

    3. 新建文件并保存

     

    图5.2.3

     

    4. 将文件加入工程

     

    图5.2.4

    5.打开文件可以直接编写程序。

    6.编写程序。

    7.调试好程序,结束。

    如图,编译无错,则可以将程序烧制到单片机中执行了。

    5.3 测试结果

    在本次实验中,测试结果如图5.3.1所示:

     

    5.3.1 测试结果图

    6. 设计总结

    6.1 本文的主要工作和成果

    系统采用了以广泛使用的单片机AT89C51为核心,配合时钟芯片DS1302,并采用LCD显示电路,键盘扫描电路所设计的一款可以进行远程调控的时钟电路。主要工作和成果如下:

    (1)介绍基于单片机的时钟电路的设计方法,并对基于单片机的时钟的应用进行了初步探讨。

    (2)介绍了时钟芯片DS1302的基本原理、特性及使用方法。对单片机软硬件资源和接口扩展都有了深入的学习。

    (3)在系统的软件仿真调试中,运用了Protues、keil等软件;学习了他们的基本操作,掌握了程序的编译过程、电路图的绘制过程。

    (4)系统设计出的实时时钟除了可以显示时间之外,还可以进行远程通信,利用远程电脑对时钟进行时间设置。课题设计取得了较好的效果,达到了课题的基本要求。

    6.2 设计中不足及其展望

    本设计重点研究实现了基于单片机与时钟芯片这种模式的时钟,从原理上对单片机和时钟芯片有了深一步的认识。但是,时钟除了能够显示基本日期时间功能外,还可以显示、设置闹钟并可在工业测量控制系统中起到定时、监控作用,以及对某些影像数据的实时记录功能等。所以说,实时时钟在工农业的监控中,它能发挥的作用会更多更大!它的这些功能还没有完善,希望以后有机会可继续完善其相应的功能。

    在基于单片机的数字时钟电路设计过程中,我学到了很多重要的东西,其中最重要的是如何将实践和理论相联系,怎样将我所学到的知识运用到我以后的工作中去。大学的课堂的学习只是在给我们灌输专业知识,而我们应把所学的用到我们现实的生活中去,此次的时钟设计给我奠定了一个实践基础。本系统的设计应用到了模拟电子技术、数字电子技术、单片机控制技术的知识,所设计的具有远程通信的时钟电路,达到了题目要求。

    这次毕业设计为使我得到了很大收获:不仅学到了许多了关于单片机方面的知识,熟悉了与单片机相关的两款软件Keil和protues7.0,提高了实验技能;而且也使我的动手能力和电路设计能力得到了极大的提高。在此次设计中,我的难点是程序的调试,由于以前仅仅学了一点C语言的皮毛,所以编一个完整的程序很是吃力!但是经过这一段时间的学习,我还是解决了一些问题。软件调试中也出现了一些问题,就是程序在编译中仿真器的设置出现了错误,从而使系统的编译通不过,给系统的调试带来了极大的不便,所以对软件的使用还须更进一步的熟练掌握。由于时间比较仓促,我只能做到达到现在这样的水平;其他的希望以后的工作中,再做深刻地研究。

    参考文献

    [1] 郭天祥.新概念51单片机C语言教程——入门,提高,开发,拓展全攻略[M].北京:电子工业出版社,2009.

    [2] 郭天祥.十天学会单片机和C语言编程

    [3] 《8051单片机C语言彻底应用》科学出版社

    [4] 《单片机原理与应用设计》北京:电子工业出版社,2008.4

    附录一 电路图

     

    附录图1. 电路图

    附录二 程序代码

    见附录

    展开全文
  • 数位DP学习小结

    千次阅读 2016-08-06 21:03:07
    数位DP,顾名思义,是对数字的每一进行DP 心得体会: 1.数位DP需要较为熟练的记忆化搜索作为基础,虽然有的题可以直接用循环进行状态转移,但记忆化搜索的状态转移更常用更容易理解 2.时刻记住:abcd这个四位数 =

    一、学习心得体会

    问题描述:

    一般体现为,定义某种性质K,问某区间内具有K性质的数的个数

    往往给的区间会很大,对区间内的每个数进行判断显然会超时

    于是数位DP登场

    数位DP,顾名思义,是对数字的每一位进行DP

    心得体会:

    1.数位DP需要较为熟练的记忆化搜索作为基础,虽然有的题可以直接用循环进行状态转移,但记忆化搜索的状态转移更常用更容易理解

    2.时刻记住:abcd这个四位数 = a*1000+b*100+c*10+d

    3.关于dp状态的保存,一般一维都是保存数字在整个数中的位置(数位),然后根据题目给定的数字的性质确定二维三维要保存什么状态

    感觉数位DP的关键就在于状态的保存(当然状态转移也很重要)一般而言,dp[i][j][k]表达的信息是:具有i性质,j性质,k性质的数的个数

    4.在记忆化搜索的过程中,对于数字abcd,搜索是从左往右搜索,但实际上计算是从右往左计算的(递归原理)

    5.数位DP需要注意所搜索的范围不能大于原本被视作字符串的那个数字(这个在记忆化搜索中常表现为一个变量标记上界)

    同时有时候0的情况也需要特别注意(具体情况具体分析吧)

    6.数位DP刚刚入门的时候觉得很难,做多了觉得万变不离其宗,代码长得都差不多,都是套路,唯一的变化也就是定义的数的属性不一样

    所以感觉数位DP的难点也就是状态的保存,针对题目给的性质保存相应的状态

    7.刚开始写数位DP的时候用循环写状态转移,感觉理解起来没有记忆化搜索清晰,于是后面都是用记忆化搜索写的了

    8.理论再强大,理解再深刻,不如多做题,做第一道题的时候感觉似懂非懂,后面做着做着也就渐渐理解了,书读百遍其义自见也是这个理

    二、从具体题目中体会

    玩了一个数位DP的专题:打开专题

    终于做完了数位DP的专题,不过也只是初窥门槛,以后还要继续努力^_^

    整体看起来,代码其实大致都一个套路,都是一个dfs 记忆化搜索,一个cal计算

    数位DP一般都是用数组的维度保存数的性质,然后dp的值表示具有这样性质的数的个数

    个人觉得记忆化搜索比迭代好理解代码看着也舒服,所有除了第一次写的D题,其他都是用记忆化写的

    然后说说这个专题,CD两题算是基础题,G题定义的数字的性质蛮新颖,但是想到怎么保存状态也是基础题

    H题在基础上加了倍数的判断

    AB两题在状态的保存上转了点弯,特别是B题还结合了状态压缩和最长上升子序列

    F题比较特别,求的不是数的个数,而是所有满足性质的数的平方和

    E题也是数位,不过保存的是二进制数的每一位

    (专题整体写下来收获蛮大的^_^)

    A - Beautiful numbers 

    题意:

    定义beautiful 数:这个数能被它的每一位整除

    例如12 能被12整除,故12beautiful

    求区间[l,r]内的beautiful数的个数

    分析:

    利用记忆化搜索把小于等于num 的数中的所有beautiful数都搜出来

    怎么搜呢?还是按照数字“位”来搜。

    现在问题是:

    1.怎么判断beautiful数?

    2.怎么保存状态?

    显然,需要将beautiful数的性质用状态保存下来。

    beautiful数需要整除它所有的非零位

    那么它只需整除它所有位的最小公倍数即可

    数字1~9的最小公倍数为2520(设为mxlcm

    考虑这样一种保存状态的方法:

    dp[i][j][k]表示长度为 i,所有数位的lcmjmxlcmk的答案

    那么需要开一个dp[20][2520][2520]的数组,类型是long long

    这数组显然是开不下的,要想办法压缩

    对这个数组的第二维,“所有数位的lcmj”,其实j的取值虽然可能达到2520

    但是j实际的数最多只有50

    于是可以考虑开一个hs数组,hs[j] = id;表示给所有数位的lcmj的编号为id

    这样一个dp[20][50][2520]的数组保存状态,那么万事俱备可以搜索了。

    搜索的具体方法在代码中介绍

    代码:

    #define mem(a,x) memset(a,x,sizeof(a))
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;
    typedef long long ll;
    /*
        若一个数能整除它的所有的非零数位,
        那么相当于它能整除个位数的最小公倍数。
        因此记忆化搜索中的参数除了len(当前位)和up(是否达到上界),
        有一个prelcm表示前面的数的最小公倍数,
        判断这个数是否是Beautiful Numbers,还要有一个参数表示前面数,
        但是这个数太大,需要缩小它的范围。
        缩小前面组成的数的范围:
        可以发现所有个位数的最小公倍数是2520,假设当前的Beautiful Numbers是x,
        那么 x % lcm{dig[i]} = 0,
        又 2520%lcm{dig[i]} = 0,
        那么x%2520%lcm{ dig[i] } = 0,x范围由9*10^18变为2520。
    
    */
    ll gcd(ll a,ll b)
    {
        return b?gcd(b,a%b):a;
    }
    ll lcm(ll a,ll b)
    {
        return a/gcd(a,b)*b;
    }
    const int mxlcm = 2520;// 0~9所有数字的 lcm
    int  dig[25];//保存数字的每一位
    ll dp[25][50][mxlcm+5];//dp[i][j][k]表示长度为 i 所有数字lcm为j  %mxlcm 为 k(即余数为k)的数的个数
    int  hs[mxlcm+5];//hs[i]表示所有数位的lcm 为 i的数的编号
    /*
        关于上界 up 的作用:
        比如数字是 543
        那么当搜到 5 的时候
        枚举 0~5 其中枚举 4 的时候可以去搜499、
        但是枚举到 5 的时候 599 是大于543的
        所以这里用 up 控制搜索到的数字在 cal计算的数字范围内
    */
    ll dfs(int len,int plcm,int pnum,bool up)//记忆化搜索
    {     //当前位      前面数字的lcm  前面的数   是否达到上界
        if (len == 0) return pnum%plcm == 0;//整个数都搜完了,即搜到个位,只需单独判断个位即可
        if (!up&&dp[len][hs[plcm]][pnum]!=-1) return dp[len][hs[plcm]][pnum];
        int n = 9;
        if (up)//到界了
        {
            n = dig[len];//达到上界的时候是dig[len],其他时候是9
        }
        ll ans = 0;
        for (int i = 0;i <= n;++i)//枚举这一位可能的数字
        {
            int nnum = (pnum*10 + i)%mxlcm;
            int nlcm = plcm;
            if (i) nlcm = lcm(plcm,i);
            ans += dfs(len-1,nlcm,nnum,up&&(i == n));//所有的可能加起来
        }
        if (!up) dp[len][hs[plcm]][pnum] = ans;
        return ans;
    }
    ll cal(ll x)//计算[1,num]中beautifun的个数
    {
        int len = 0;//将数字的每一位保存在数组dig中
        while (x)
        {
            dig[++len] =x%10;
            x/=10;
        }
        return dfs(len,1,0,1);//传参
    }
    void init()//hash预处理
    {
        int id = 0;mem(dp,-1);//记忆化dp只初始化一次即可
        for (int i = 1;i <= mxlcm;++i)
        {
            if (mxlcm%i == 0) hs[i] = ++id;
        }
    }
    int main()
    {
        int T;init();
        scanf("%d",&T);
        while (T--)
        {
            ll l,r;
            scanf("%I64d %I64d",&l,&r);
            printf("%I64d\n",cal(r) - cal(l-1));
        }
        return 0;
    }
    

    B - XHXJ's LIS

    题意:

    当把数当字符串看的时候,求区间[l,r]最长公共子序列的长度为K的数的个数

    我个人觉得这题出的很好,将数位DP,状态压缩和最长公共子序列的nlogn算法结合起来

    另写了题解: HDU 4352 XHXJ's LIS(数位DP+状压)


    C - 不要62

    题意:

    区间[l,r]内数字的数位不含62且不含4的数的个数

    分析:

    这题数据小,可以水过,用dp[i]表示前i个数中满足的数的个数

    if ok(i) dp[i] = dp[i-1] + 1  else dp[i] = dp[i-1]  先求出所有dp,然后直接输入输出

    用正常的数位DP的方法写的话:

         状态保存:
        dp[len][0]表示长度为len 且不含4和62,最高位不是2的个数
        dp[len][1]表示长度为len 且不含4和62,最高位是2的个数
        状态转移:
        dp[i][0] = 8*dp[i-1][0] + dp[i-1][1] (除去4还有8种可能)
        dp[i][1] = 7*dp[i-1][1] + dp[i-1][1] (除去4还要除去6,否则会构成62)

    正常的循环可以写,不过感觉记忆化搜索更好理解写着更清晰,故而用记忆化写的

    代码:

    #define mem(a,x) memset(a,x,sizeof(a))
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<set>
    #include<stack>
    #include<cmath>
    #include<map>
    #include<stdlib.h>
    #include<cctype>
    #include<string>
    using namespace std;
    typedef long long ll;
    /*
        状态保存:
        dp[len][0]表示长度为len 且不含4和62,最高位不是2的个数
        dp[len][1]表示长度为len 且不含4和62,最高位是2的个数
        状态转移:
        dp[i][0] = 8*dp[i-1][0] + dp[i-1][1] (除去4还有8种可能)
        dp[i][1] = 7*dp[i-1][1] + dp[i-1][1] (除去4还要除去6,否则会构成62)
    
    */
    int dp[10][2];
    int dig[10];//保存数字的每一位
    int dfs(int len,bool is6,bool up)//当前搜的位,这一位的前一位是不是6,是否为上界
    {
        if (len == 0) return 1; //dp[0][0] = 1;
        if (!up&&dp[len][is6]!=-1) return dp[len][is6];
        int ans = 0;
        int n = 9;if (up) n = dig[len];
        for (int i = 0;i <= n;++i)
        {
            if (i==4) continue;// 4
            if (is6&&i==2) continue;// 62
            ans += dfs(len-1,i==6,up&&(i == n));
        }
        if (!up) dp[len][is6] = ans;
        return ans;
    }
    int cal(int x)
    {
        int len = 0;
        while (x)
        {
            dig[++len] = x%10;
            x/=10;
        }
        return dfs(len,0,1);
    }
    int main()
    {
        mem(dp,-1);
        int l,r;
        while (scanf("%d %d",&l,&r)&&(l||r))
        {
            printf("%d\n",cal(r)-cal(l-1));
        }
        return 0;
    }
    

    D - Bomb

    本渣的第一道数位DP题,对着别人的题解啃了半天,用循环来进行状态转移

    (后来深刻体会到记忆化搜索写着更清晰更好理解!)

    题意:

    区间[1,r]中数位不含49的数的个数(感觉数位DP的题意都是一个调调)

    分析:

        dp[i][0] 表示长度为 i 的数中 不含 49 的数的个数
        dp[i][1] 表示长度为 i 的数中 不含 49 但最高位为 9 的数的个数
        dp[i][2] 表示长度为 i 的数中 含49的数的个数

            dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];
            dp[i][1] = dp[i-1][0];
            dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1];

    先把表打好,然后对于具体输入的r具体处理

    代码1(循环):

    #define mem(a,x) memset(a,x,sizeof(a))
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<set>
    #include<stack>
    #include<cmath>
    #include<map>
    #include<stdlib.h>
    #include<cctype>
    #include<string>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int N = 20;
    ll dp[N][3];
    void init()
    {
        dp[0][0] = 1;
        for (int i = 1;i <= N;++i)
        {
            dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];
            dp[i][1] = dp[i-1][0];
            dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1];
        }
    }
    int len;
    ll s[30];
    void cal(ll x)
    {
        len = 0;
        while (x)
        {
            s[++len] = x%10;
            x/=10;
        }
    }
    int main()
    {
        int T;scanf("%d",&T);
        init();
        while (T--)
        {
    
            ll n;
            scanf("%I64d",&n);
            ++n;cal(n);
            int lr = 0;ll sun = 0;bool fd = 0;
            for (int i = len;i >= 1;--i)
            {
                sun += (ll)(s[i])*dp[i-1][2];
                if (fd) sun += (ll)(s[i])*(dp[i-1][0]);
                if (!fd&&s[i] > 4)
                {
                    sun += dp[i-1][1];
                }
                if (lr == 4&&s[i] == 9) fd = 1;
                lr = s[i];
            }
            printf("%I64d\n",sun);
        }
        return 0;
    }
    

    代码2(记忆化搜索):

    #define mem(a,x) memset(a,x,sizeof(a))
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<set>
    #include<stack>
    #include<cmath>
    #include<map>
    #include<stdlib.h>
    #include<cctype>
    #include<string>
    #define Sint(n) scanf("%d",&n)
    #define Sll(n) scanf("%I64d",&n)
    #define Schar(n) scanf("%c",&n)
    #define Sint2(x,y) scanf("%d %d",&x,&y)
    #define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
    #define Pint(x) printf("%d",x)
    #define Pllc(x,c) printf("%I64d%c",x,c)
    #define Pintc(x,c) printf("%d%c",x,c)
    using namespace std;
    typedef long long ll;
    /*
    	记忆化绝对比循环好理解,我发誓~~~^_^ 
    	dp[len][four][have]表示正在处理的位长度为len
    	正在处理的前面一位是不是4
    	已经处理过的位里面是不是已经有49了 
    */
    ll dp[22][2][2];
    int dig[22];
    ll dfs(int len,bool four,bool have,bool up)
    {
    	if (len == 0) return have;
    	ll &ot = dp[len][four][have];
    	if (!up&&~ot) return ot;
    	int n = 9;if (up) n = dig[len];
    	ll ans = 0;
    	for (int i = 0;i <= n;++i)
    	{
    		bool newhave = have;
    		if (four&&i == 9) newhave = 1;
    		ans += dfs(len-1,i==4,newhave,up&&i==n);
    	}
    	if (!up) ot = ans;
    	return ans;
    } 
    ll cal(ll x)
    {
    	int len = 0;
    	while (x)
    	{
    		dig[++len] = x%10;
    		x/=10;
    	}
    	return dfs(len,0,0,1);
    }
    int main()
    {
    	mem(dp,-1);
        int T;Sint(T);
        while (T--)
        {
        	ll n;Sll(n);
        	Pllc(cal(n),'\n');
    	}
        return 0;
    }


    E - Round Numbers

    题意:求区间[l,r]内二进制数中0比1多的数的个数

    分析:之前做的都是十进制数的数位DP,这个可以转换成二进制数的数位DP(花神的数论题也是二进制上的数位DP)

    dp[i][j][k]中i,j,k分别表示长度,0的个数,1的个数,记忆化搜索的时候多传的两个参数分别表示是否到达上界,前一位是否为0

    代码:

    #define mem(a,x) memset(a,x,sizeof(a))
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<set>
    #include<stack>
    #include<cmath>
    #include<map>
    #include<stdlib.h>
    #include<cctype>
    #include<string>
    using namespace std;
    typedef long long ll;
    int dig[70];
    ll dp[70][70][70];//长度 0的个数  1的个数 
    ll dfs(int len,int zero ,int one,bool up,bool z)
    {
    	if (len == 0)
    	{
    		return z||(zero>=one);
    	}
    	ll &ot = dp[len][zero][one];
    	if (!up&&!z&&ot!=-1) return ot;
    	int n = 1;if (up) n = dig[len];
    	ll ans = 0;
    	for (int i = 0;i <= n;++i)
    	{
    		if (z&&i==0) ans += dfs(len-1,0,0,up&&(i==n),z&&(i==0));
    		else ans += dfs(len-1,zero + (!i),one+i,up&&(i==n),z&&(i==0)); 
    	} 
    	if (!up&&!z) ot = ans;
    	return ans;
    } 
    ll cal(ll x)
    {
    	int len = 0;
    	while (x)
    	{
    		dig[++len] = x%2;
    		x/=2;
    	}
    	return dfs(len,0,0,1,1);
    }
    int main()
    {
        ll l,r;mem(dp,-1);
        while (scanf("%lld %lld",&l,&r) == 2)
        {
        	printf("%lld\n",cal(r)-cal(l-1));
    	}
        return 0;
    }



    F - 吉哥系列故事――恨7不成妻

    这个题目不同于一般的数位DP求区间内具有某性质的数的个数,而是求区间内具有某性质的所有数的平方和

    感觉蛮厉害的样子,另写了题解: HDU 4507 吉哥系列故事——恨7不成妻(数位DP)


    G - Balanced Number

    题意:

    求区间[l,r]内的平衡数的个数

    所谓平衡数是指,把这个数的某一数位设置为支点。支点左右两边按|i - p|*dig计算力矩,如果能找到支点使左右力矩相等就是平衡数

    例如4139    取3为支点,左边力矩 = 4*2+1*1  = 9,右边力矩 = 9*1 = 9所有是平衡数

    分析:

    还是根据数的性质保存状态,显然数的性质涉及到力矩,支点的位置

    所以dp[i][j][k] :

                                              i : 正在处理的数位
                                              j : 支点的位置
                                             k : 左右力矩之和(正负算,为 0 就是平衡的)
                                            dp[i][j][k]就是具有上述性质的数的个数

        dp[i][j][k] = dp[i-1][j][ k + dig*(i-j)]
        其中 dig 为数位 i 处枚举的可能的数字

        状态转移中j没有转移?支点的位置需要另外枚举

    枚举支点位置?会不会出现算某个位置的时候算了一遍数字x,算另一个位置的时候又算了一遍x这样算重复的情况?

    想一下,一个数如果是平衡数,那么它的支点位置必然是固定的(0除外)

    所以不会算重复,只有最后把重复的0减去就好,0算了len遍,故重复的0有(len-1)个

    这里提一个事,这题的dp[i][j][k]保存了3个维度的信息,但是实际上,它在状态转移的时候第二维的j并没有改变

    看代码里面的dfs的过程也是,传入的一个参数p从来都没有变过,为什么不省去这一维呢?

    首先,dfs的时候确实可以不传参数p,直接让其在全局里面,然后枚举位置的时候改变其值,每次递归的时候可以直接用

    但是dp还是应该保存这一维,因为题目是多组数据,秉着算过就记录下来的原理,可以为后面更多组数节约时间

    前面B题里面也有一维没有参与状态转移,但是依旧保存下来了是同样的原理(B题的dfs没有传那个不变的参数K)

    代码:

    #define mem(a,x) memset(a,x,sizeof(a))
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<set>
    #include<stack>
    #include<cmath>
    #include<map>
    #include<stdlib.h>
    #include<cctype>
    #include<string>
    using namespace std;
    typedef long long ll;
    /*
        dp[i][j][k] :
                    i : 正在处理的数位
                    j : 支点的位置
                    k : 左右力矩之和(正负算,为 0 就是平衡的)
                    dp[i][j][k]就是具有上述性质的数的个数
    
        dp[i][j][k] = dp[i-1][j][ k + dig*(i-j)]
        其中 dig 为数位 i 处枚举的可能的数字
    
        状态转移中j没有转移?支点的位置需要另外枚举
    */
    ll dp[22][22][1600];//9*(1+2+3......+18) = 1539
    int dig[22];//数字数位上的数字
    ll dfs(int len,int p,int sum,bool up)//前3个参数对应dp3个维度的意义,up标记上界
    {
        if (len == 0) return sum==0;
        if (sum < 0) return 0;
        if (!up&&dp[len][p][sum]!=-1) return dp[len][p][sum];
        ll ans = 0;
        int n = 9;if (up) n = dig[len];
        for (int i = 0;i <= n;++i)
        {
            ans += dfs(len-1,p,sum+i*(len-p),up&&(i==n));
        }
        if (!up) dp[len][p][sum] = ans;
        return ans;
    }
    ll cal(ll x)
    {
        if (x == -1) return 0;//这题的 l 可以为 0,l-1就是-1了
        int len = 0;
        while (x)
        {
            dig[++len] = x%10;
            x/=10;
        }
        //需要枚举支点的位置
        ll ans = 0;
        for (int i = 1;i <= len;++i)
        {
            ans += dfs(len,i,0,1);
        }
        return ans - (len - 1);//减去重复的0
    }
    int main()
    {
        int T;mem(dp,-1);
        scanf("%d",&T);
        while (T--)
        {
            ll l,r;
            scanf("%I64d %I64d",&l,&r);
            printf("%I64d\n",cal(r)-cal(l-1));
        }
        return 0;
    }
    


    H - B-number

    题意:

    求区间[1,r]内数位含13且可以整除13的数个数

    分析:

    含13的话类比第D题不要49,整除13类比F题整除7(都是一个调调)

    直接类比D题和F题去做,这里就不多说直接上代码了:

    PS:网上看了一下别人的题解,别人保存的状态好像和我的有点差别

            不过我的想法也很自然,反正自己看得蛮舒服的。。。。(主要是受前面D题F题的影响,自然而然的思想^_^)

    #define mem(a,x) memset(a,x,sizeof(a))
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<set>
    #include<stack>
    #include<cmath>
    #include<map>
    #include<stdlib.h>
    #include<cctype>
    #include<string>
    using namespace std;
    typedef long long ll;
    /*
        dp[i][j][k][l]:
                        i : 正在处理的数位
                        j : %13 = j的数
                        k :这一位的前一位是否为 1(是--1,否--0)
                        l :前面是否已经含 13(是--1,否--0)
    */
    ll dp[22][13][2][2];
    ll dig[22];
    ll dfs(int len, int r,bool is1,bool has,bool up)
    {
        if (len == 0) return r == 0&&has;
        if (!up&&dp[len][r][is1][has]!=-1) return dp[len][r][is1][has];
        ll ans = 0;
        int n = 9;if (up) n = dig[len];
        for (int i = 0;i <= n;++i)
        {
            bool nhas = has;
            if (is1&&i==3) nhas = 1;//已经有了13
            ans += dfs(len-1,(i+r*10)%13,i==1,nhas,up&&(i==n));
        }
        if (!up) dp[len][r][is1][has] = ans;
        return ans;
    }
    ll cal(ll x)
    {
        int len = 0;
        while (x)
        {
            dig[++len] = x%10;
            x/=10;
        }
        return dfs(len,0,0,0,1);
    }
    int main()
    {
        ll r;mem(dp,-1);
        while (~scanf("%I64d",&r))
        {
            printf("%I64d\n",cal(r));
        }
        return 0;
    }
    


    展开全文
  • 你是想读书,还是想完书?

    千次阅读 2013-02-21 10:45:36
    到这篇文章,感觉非常不错,转载至此,以留念! 从左岸转过来一篇文章,原文地址 http://www.zreading.cn/archives/3621.html,有趣的是原文前半部分最早出自豆瓣,后半部分出自知乎上一个问题精彩回答。一...

     读到这篇文章,感觉非常不错,转载至此,以作留念!

     从左岸转过来一篇文章,原文地址 http://www.zreading.cn/archives/3621.html,有趣的是原文前半部分最早出自豆瓣,后半部分出自知乎上一个问题精彩回答。一起来看看吧,至于标题的问题,看完你会自己答案的。以下是左岸原文


    以前,读书前会很想读一本书,但实际读书时,经常是“想读完书”,而不是“想读书”。这种想法经常会让我的生活变得很痛苦,当你做一件事想着快点做完时,你的心思其实已经不在这件事上了。

    这个问题在我大学时困扰了我很久。我没有意识到这本身其实是一个价值观问题,以至于我常在一些时间管理的书中寻找答案。那些书都只能让你更高效地“做完事”,却不能让你在做的过程中更投入一分。

    直到后来离开学校,了解了一小部分禅宗思想,我开始豁然开朗。禅宗讲求摒除心中的杂质,全部精神专注于当下,摒弃过去摒弃未来,任何的多余的念头都可能使你正在做的事情不纯粹。禅宗上,这叫“正念”,我非常非常欣赏。

    想想看,你去旅行,那你是为了旅行和生活本身呢,还是为了旅行回来能增加一点谈资、写一篇游记呢?答案是显然的。

    人生也是一样,如果你一心只等着功成名就家财万贯衣食无忧的那一天,就好像你旅游时只等着回去写游记和炫耀一样,旅行本身就失去了意义。

    生活就像这样的旅行,我们今天读的每一本书,写的每一个字,迈的每一个步,做的每一件事,就是这趟旅行的一部分。如果我们不能专注于它本身并享受这种过程,那整个生活就会变成急不可耐的煎熬。

    回到读书上来,现在我觉得对书的“量”的追求是完全无意义的。如果我在读一本书时专注于其中,不仅可以获得远比匆匆翻过更深入的东西,而且还能为人生增加不曾虚度的有趣有意义的几天或几小时。

    对了,在很多领域都有一个词叫“flow”,描述人们沉浸在某事中获得的愉悦状态,根据我粗浅通俗的理解,禅宗正念的目标,就是把这种状态扩展延伸到你生命的每一秒。


    知乎上有个很好的问题:大学两年读了大概200本书,为什么感觉读书的价值还是没有体现出来呢

    其中有些精彩的回答道出了个中缘由——“书不在于读完它,而在它成为你人生的一部分。”

    大学时,一位很有才华的心理学老师说过的一句话,让我终身难忘:“很多同学喜欢说自己一天能读多少页的书,有些人一天能读50页,有些人能读100页。可是一旦你用‘页数’为单位来度量读书这种行为时,从一开始你就错了。”

    同理,如果你用读了多少本书来形容你的读书经历,这种思路,从一开始就错了。

    如果你认真读到了书里去,是不会care、甚至会完全忽略掉今天读了多少页,今年读了多少本的;当你沉迷于书中绚烂多彩的世界,当你的观念被翻天覆地地革新,是不会care、甚至会完全忽略掉今天读了多少页,今年读了多少本的。

    当我们看手表的时候,常是快等不及了;当我们数书页的时候,常是快看不下去了;当我们念叨看了几本书的时候,常是连书名都记不全了。所以,数多少页、多少本这行为本身,就说明你已经败了。

    很多时候,一个人对待知识和思想的态度,就体现在用什么东西去丈量它。

    如果有人问一位读书而有大成之人:你因何而脱胎换骨?你因何而涅磐重生?这些问题,他该如何作答?他说:”我因200本书而脱胎换骨,我因1000本书而涅磐重生“,如何?

    阅读是一种享受,但如果读完一本书,没有新的体验,完全不同的视角和观点、不能对你的思维有所改变、特别是读完一本好书之后,想不清楚、说不清楚、写不清楚、也从来没有行动过,那你看书是在浪费时间。

    学而悟道,有时候一本书就够了,有时候一万本都不够。这取决于,你读了什么书,更重要的是,你是如何读的:你有没有读进去把自己活埋在里面,又有没有读出来敲打出一个新的自己。

    有些书,是一代宗师级的人物,把他们毕生的智慧熔铸在一本书里面;有些书,是一个领域的开疆拓土之作,从一片混沌中劈出一个新世界;有些书,是一个领域的集大成之作,观点纷繁,气象万千;有些书,如盗梦空间一般有几层境界,你多读一遍就多梦到一层。对这些书,你若只是都当成那两百分之一,花上一个星期匆匆读完,读后即扔,只摘下几条金句供日后泡妞之用,难道这就算读过了吗?

    有些书,要用心血去读;有些书,要用足够的经历去读;有些书,是要绞尽最后一粒脑细胞去读;有些书,是一辈子都读不完读不透……

    看书的方法,不仅要看作者写了什么(一层),还要琢磨文字背后的意蕴,那些弦外之音(二层),还要去思考作者为什么要写这些、要这样写(三层),还要去想想 看作者用了什么样的框架和策略在组织这本书,以及在各种细微处又用了什么样的方法和技巧(四层),当然更重要的是,以上的这些分析对你自己的现实和精神世 界能带来什么样的帮助,是否能启发你、引导你、改变你……(五层)

    于是,一本值得都烂读透的书,就需要你去读五遍、十遍去读烂读透它。

    于是乎,和很多人的答案相反:所谓200本,你不是读少了,而是读多了、读水了、读浅了!

    其实你的状态一点都不特殊,你和许多人一样,以为自己在读书,其实是在集邮。

    最后,建议你重新拿起一本你最崇敬的书,换一种方式,再读一遍、两遍、三遍……

    原文:http://www.douban.com/note/217444792/

         也许这是一个被讨论过多次问题,不过偶尔重新看一次也会有不同的收获。一篇短文,三个不错的阅读站点。不知道有时候是不是我们已经忘了我们原本的初衷呢?
    展开全文
  • 【论文夜】陈天琦神Neural Ordinary Differential Equations(NuerIPS2018最佳paper) 在最近结束的 NeruIPS 2018 中,来自多伦多大学的陈天琦等研究者成为最佳论文的获得者。在与机器之心的访谈中,陈天琦的导师...
  • 立即只能源操作使用,不能目的操作. 示例: MOV AL, 25 MOV SI,OFFSET DATA1 注意: 由于传送的数据可能是字节,也可能是字,源操作与目的操作 的类型应一致。 < 3 > 寄存器与存储器之间的...
  •  bs = bytes 同时设置/写缓冲区的字节(等于设置ibs和obs)。  cbs = byte 一次转换bytes字节。  count=blocks 只拷贝输入的blocks块。  conv = ASCII 把EBCDIC码转换为ASCIl码。  conv = ebcdic ...
  • 这块简单易制作的0-30VSTC单片机数字电压表,被测电压经限流电阻接到AD检测端并由分流电阻分流,读出8(256)的AD数据,由AD值计算出AD端电压,即分流点电压,由此电压计算出分流电流,再由此电流计算出输入电压。...
  • Catalan——卡特兰

    千次阅读 2017-04-14 11:12:06
    转自:Catalan——卡特兰 Catalan——卡特兰  今天阿里淘宝笔试中碰到两道组合数学题,感觉非常亲切,但是笔试中失踪推导不出来 后来查了下,原来是Catalan。悲剧啊,现在整理一下 一、Catalan的...
  • 英语中的数字读法

    千次阅读 2012-04-05 14:40:51
    首先掌握三位以内数字的读法,因为它是多位数字的基础,一旦熟练掌握,再借助一个逗号,便可轻松应付四位以上任何庞大的数字。我们可以通过例子来说明这一点。  ①3—5位数的读法  202读作:two hundred(and...
  • 关于读书的几个问题

    千次阅读 热门讨论 2013-09-30 08:19:10
    读书,并不是穷酸秀才秀穷秀酸的时候才出来卖弄于人的。...如今已经不像古时那般可之书太少,但如今读书的风气却不振,原因在于很多人在受教育的过程中完全为了考试而读书,结果是非考不学,非教不
  • 一个合格的程序员应该过哪些书

    万次阅读 多人点赞 2012-08-14 15:59:34
    编者按:2008年8月4日,StackOverflow 网友 Bert F 发帖提问:哪本最具影响力的书,是每个程序员都应该的? “如果能时光倒流,回到过去,作为一个开发人员,你可以告诉自己在职业生涯初期应该一本, 你会选择...
  • 名人的读书方法

    千次阅读 2011-10-10 16:52:30
    为消遣而读书,常见于独处退居之时,为装饰而读书,用于高谈阔论之中;为增长才干而读书,主要在于对事物的判断和处理。 读书费时太是怠惰,过分的藻饰装璜是矫情,全按书本条文而断事是十足的学究气。读书使...
  • 目送 “我慢慢地、慢慢地了解到,所谓父子母女一场,只不过意味着,你和他的缘分就是今生今世,不断地在目送...我的答案是多读经典书。方向对了即使慢点,总会走向成功的终点。而该哪些书,我带来了五份经典书单。
  • feof()多读一次的解决方法

    千次阅读 2015-06-10 14:23:08
    只有当文件位置指针(fp->_ptr)到了文件末尾,然后再发生/写操作时,标志(fp->_flag)才会被置为含有_IOEOF。 然后再调用feof(),才会得到文件结束的信息。 因此,如果运行如下程序: char c; while(!feof...
  • 英语数字的读法(ZT)

    千次阅读 2010-04-20 21:01:00
    经常有友友在平台一对一聊天中问到英语数字的读法,整理了一下,供大家参考。 (1)基数词的读法 我们先从基数词入手。... ①3—5位数的读法 202读作:two hundred(and)two 234读作:two hundred(and)thirty
  • 蓝桥杯 的读法 C语言

    千次阅读 2018-08-20 21:08:55
    基础练习 的读法 /题目: Tom教授正在给研究生讲授一门关于基因的课程,有一件事情让他颇为头疼:一条染色体上有成千上万个碱基对,它们从0开始编号,到几百万,几千万,甚至上亿。 比如说,在对学生讲解第...
  • 吴军老师《大学之路》后感。
  • 《统计陷阱》后感

    千次阅读 2016-05-26 21:20:41
    《统计陷阱》后感 知道这本的时候还是从我在大一刚进辩论队的时候,在日常的队训中听到队长建议阅读这本书的,之前总说要呢,结果各种推过,现在终于静下心来阅读这本书了。看完之后的感触到真不少,而且总想着...
  • 根号2以及π的计算--关于无理的畅想

    万次阅读 多人点赞 2017-07-02 12:38:43
      其实,在数学方面,西方要强大得,但因为我个人就是研究希腊罗马近东的,所以为了避嫌就不说西方多么优秀了,本文我以魏晋时期刘徽的割圆术为基底,重现一下当年是怎么用朴素的手段算π的。和 2 √ \sqrt{2} ...
  • 一生的读书计划

    万次阅读 2008-01-17 16:33:00
    玛格丽特从小受到父亲的加倍疼爱,在法国北部、南部和巴黎度过了优裕的童年和少年时代,得到数位女管家的呵护和家庭教师的悉心指导。与父亲一样,自青年时代起,尤瑟纳尔即长期奔走于欧洲多国和美加之间。1939年第二...
  • 读书笔记:《人工智能》

    万次阅读 2017-10-31 00:17:52
    目前的计算机视觉系统在看过百万张或更自行车的照片后,很容易辨别出什么是自行车,什么不是自行车,这种需要大量训练照片的学习方式看上去还比较笨拙。 尽管研究者提出了迁移学习等新的解决方案,但从总体上...
  • 数字频率计设计

    千次阅读 2020-10-21 16:56:53
    设计任务与要求 1、设计任务 设计并实现一个数字频率计。 2、基本要求: 测频率范围:10Hz ~ 10K Hz。为保证测量精度分为三个频段: ...测量结果用三半导体数码管显示,要求显示数码稳定清晰...
  • 图 一个已知8个棱角密度(Density)值的体素(黑点指示了棱角处的正密度值,每个棱角为一个“(byte)”,用于在总共8的情况中进行判断) 使用GPU来生成地形块所需要的多边形,这个块进行进而被细分成 32 x ...
  • 在开发中,如果需要使用个按键时,使用ADKEY,往往可以节省很IO口,可以节省资源。下面,简单介绍一下ADKEY的使用与经验分享。ADKEY原理:通过不同的电阻进行分压,使每个key按下时,IO口到电压值不同,来确认...
  • 一篇懂无线充电技术(附方案选型及原理分析)

    万次阅读 多人点赞 2017-09-02 10:27:12
    一文懂无线充电技术(附方案选型及原理分析) 0.背景 1.无线供电特点 2.无线供电原理及实现方式 3.现有解决方案分析 4.FAQ及相关测试 5.参考资料 0.背景 现今几乎所有的电子设备,如...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 138,273
精华内容 55,309
关键字:

多位数的读作