精华内容
下载资源
问答
  • 相传是按照十二生肖出没的时间来命名时辰的,那么,个时辰相当于现在的个小时呢?起来看看吧!古时候将昼夜分为十二时辰,每段时间称为时辰。个时辰是现在的两小时,时辰从半夜算起,子时是从半夜十一点...
    b99c847419a79d59f2a293ca55324af7.png

    古时候将一天划分为十二个时辰,分别是子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥。相传是按照十二生肖出没的时间来命名时辰的,那么,一个时辰相当于现在的几个小时呢?一起来看看吧!

    古时候将一昼夜分为十二时辰,每一段时间称为一时辰。一个时辰是现在的两小时,时辰从半夜算起,子时是从半夜十一点到一点。

    而所谓的午时是指中午十一点到下午一点,亥时是指晚上九点到半夜十一点。除此之外,古时候的更也是按照时辰来算的。

    一般来说,更分为五更。一更指的是晚上七点到晚上九点;二更是晚上九点到半夜十一点;三更和子时时间是一样的,为半夜十一点到一点。

    而四更是凌晨一点到凌晨三点,五更指的是凌晨三点到凌晨五点。古时候有专门提醒人们时间的职业,叫做“更夫”,是会分别在五更的时候打更,提醒人们时间。

    一刻钟等于多少分钟?

    古时候将一昼夜分为十二时辰,而一时辰等于八刻。一时辰等于现在的两小时,那么一刻就等于现在的十五分钟。古时候所谓的“午时三刻”指的是现在的中午十二点四十五分。

    阴阳家说,一天中阳气最盛的不在午时,而是在午时三刻,也就是现在的十一点四十五分或者十二点四十五分。

    展开全文
  • 五(3)班 李楚灵 指导老师 胡学军缘 起 我从数学报上看到了这样一道题:“传说,在月圆之夜,一群黑猫会排成座塔,每层的黑猫数都是该层的平方数(如果是第层,黑猫则有1的平方只),一共有层,问,一共有只...
    慢慢阅读   慢慢成长b0f5916d2e7e4712f840f17f9c77664a.png

    80d135e932ef0a61ad5e71cabb3c36d7.png

    乐清市康德寄宿学校  五(3)班    李楚灵  指导老师    胡学军缘 起  我从数学报上看到了这样一道题:“传说,在月圆之夜,一群黑猫会排成一座塔,每一层的黑猫数都是该层的平方数(如果是第一层,黑猫则有1的平方只),一共有九层,问,一共有几只黑猫?”平方数是什么?我上网查了查,平方数指某个数的二次方,也就是某两个相同的因数相乘,那么,平方数到底蕴含着怎样不为人知的秘密呢?一个数的二次方为什么称为平方呢?我心中的谜团越来越多,所以,我决定深入研究平方数,来解开我心中的一个个疑问。

    初出茅庐——1-10之平方数研究

    我深入研究平方数,列出了表一。

    表一

    原    数

    平方数

    变    化

    1

    1

    +3=4

    2

    4

    +5=9

    3

    9

    +7=16

    4

    16

    +9=25

    5

    25

    +11=36

    6

    36

    +13=49

    7

    49

    +15=64

    8

    64

    +17=81

    9

    81

    +19=100

    10

    100

    通过观察图表我发现:①相邻两数的平方之间的差相等;②相邻两数,前一个平方数加上原数再加上相邻的原数(大数)等于下一个数的平方数,如1是1的平方,1+1+2=4=22那么,为什么规律②能够成立呢?它的奥秘究竟是什么呢?我想起数学老师曾说过:“要解决复杂的问题,需从简单的问题入手”,于是,我从画图开始分析,试图从中找到答案(如图1) 649f2ebf5193457e6665705e8c7a6d4e.png太神奇了,我在图中很快发现了规律,如下:如果设原正方形为3×3的模样,想要变成4×4的正方形,需要先加上3,变成了4×3的小长方形,再加上4,就能变成一个完整的4×4的正方形,以此类推:12+1+2=22=4,22+2+3=32=9,32+3+4=42=16,……经过多次尝试,我的猜想成立。如果用字母表示,那么这个规律可以概括为:a2+a+(a+1)=(a+1)2如果把算式反一下,又会是怎样的呢?带着这个问题,我进一步研究:

    22-12=2+1

    32-22=3+2

    42-32=4+3

    52-42=5+4

    ……

    我发现,相邻两数的平方差等于两数的原数相加,我推导出了相邻两数的平方差公式:a2-b2=a+b(a、b必须为相邻两数)我惊喜万分,知道了规律后,我忍不住让我妈考考我。192-182等于几?”“37!”“272-262等于几?”“53!”有了公式,我算得比计算器还快,连老妈也被我“吓得不轻”啊!乘风破浪——11-20之平方数研究对于10以内的数的规律如此,其它数还有哪些规律呢?我继续对11-20的平方数进行研究。

    表二

    原数

    平方数

    变化

    11

    121

    +23=144

    12

    144

    +25=169

    13

    169

    +27=196

    14

    196

    +29=225

    15

    225

    +31=256

    16

    256

    +33=289

    17

    289

    +35=324

    18

    324

    +37=361

    19

    361

    +39=400

    20

    400

    通过上表观察发现:③平方数个位数十个一组,周期均为1、4、9、6、5、6、9、4、1、0。(平方数的个位没有2,3,7,8)④其它规律都不变。我心想,竟然我研究出了相邻两数的平方差,那为何不坚持到底,继续研究出不相邻两数的平方差呢?于是,我的大脑飞快地运转起来,开始了画图巧算平方差(不相邻)之旅。巧求平方差(不相邻)

    表三

    2264ad9487597245a49a1a097d0e3a40.png

    152-32=(15+3)×(15-3)

    9ceeb29eda61af4ea0dbca2288c586c0.png

    192-42=(19+4)×(19-4)

    59f56c61aac8894ee0b67f3e671426d3.png

    132-32=(13+3)×(13-3)

    7bc46512a79cd81b83c6bb023a6521c8.png

    172-42=(17+4)×(17-4)

    27d48e91ffcb83e51da5d90f0a6dfd66.png

    232-52=(23+5)×(23-5)

    d8a00e0a099e615edfbb5cde53bc8312.png

    a2-b2=(a+b)×(a-b)

        通过画图计算比较,我们不难发现152-32还剩一长3,宽是2的长方形和一个长15宽2的长方形。如果把这个图形拼接起来,就是一个大长方形,它的长是15+3,宽是15-3。由此我得出:152-32=(15+3)×(15-3)。我猜想:两个数的平方差是不是等于两个数的和乘以两个数的差”呢?

    我再次画图验证192-42。得出:192-42=(19+4)×(19-4)

    由此,我推出平方差公式:a2-b2=(a+b)(a-b)。

    另辟大道——寻觅立方数13-103

    表四

    原数

    立方数

    1

    1

    2

    8

    3

    27

    4

    64

    5

    125

    6

    216

    7

    343

    8

    512

    9

    729

    10

    1000

     有了上面的基础,我信心满满地列出了表四,试着找立方数的规律。我首先从数字表面去看,既不是等差数列,也不是斐波那契数列,也没有倍数的关系。然后,我将前一个立方数(1)乘2,加上原数(1)乘2,再加上下一个原数(2)乘2,正好等于下一个立方数(8),我欣喜若狂,再换了一组数据试一试,不行!我从数字的和、差、积、商去试(如表四),再去用加、减、乘、除去算,结果毫无章法。经过几天冥思苦想,我猜想:可以利用平方数的规律去做行吗?我尝试着用原数乘以平方数,果然,原数×平方数=立方数!为什么会这样呢?它有什么规律呢?我带着这些问题继续探究:

    表五

    1+8=9×

    8-1=7×

    1×8=8×

    9不等于27

    7不等于27

    8不等于27

    8+27=35×

    27-8=19×

    8×27=216×

    35不等于125

    19不等于125

    216不等于125

    用和不行

    用差不行

    用积不行

      首先,我想到立方数是三维空间,立体数。其推导公式应是原数×原数×原数=立方数,而平方数是二维空间,平面数,其推导公式应是原数×原数。对比数据,综合分析,立方数不就比平方数多乘了一个原数吗?所以只要拿平方数再乘一个原数就可以了,这算什么规律呢?在没有办法的情况下,我只好向“度娘”求救,可这“抠门”的问题连度娘也不知道,看来立方数与立方数之间毫无规律。其原因可能是因为立方数是由三个数相乘,融入的元素比较多,所以没规律。

    92e2e0f232230885eefdc14ced9173d7.png

    我心想:立方差立方和会不会有公式呢?于是我试着去发现立方和与立方差中的奥秘,我试着在电脑上做了个图,我将它们的差分成三块,第一块的大小是a2×(a-b),第二块是b2×(a-b),第三块长方体的面积为ab(a-b)。根据乘法分配律,我们可以将其公式转换为(a-b)×(a2+b2+a×b)。经过反复尝试,我得出了这一规律。再次验证:5³-3³=98,(5-3)×(52+32+5×3)=98,5³-3³=(5-3)×(52+32+5×3)。有了公式,我妈问我:“153-113等于几?”我套入公式,(15-11)×(152+112+15×11)=2044,再拿计算器一算,完全正确,我欣喜若狂!挑战巅峰——转战平方和与立方和有了之前求平方差和立方差的经历,我对立方和的探究更加强烈,寻思着能不能求出平方和和立方和呢?我从简单一些的“平方和”开始,我想到的方法是“补全法”,那其简化公式应该是a(a+b)-ab,然而这并没有简化,并且更麻烦了,我实在是想不出办法了,只好“虚心请教”。我上网搜索“平方和公式”,只蹦出了“完全平方和公式”,我打开一看,这公式是a2+b2+2ab,那么如果想求平方和,公式应是(a+b)2-2ab,但最终的计算还是没有简便一些,“有时候人就要老实一点,好好算”。这话用在求平方和上可真恰当,无奈之下,我只好向大家宣布平方和没有简便运算,然后开始另一道工序:研究立方和,同样,我在草稿上画了一个透视图(做立体图形容积题必用),再把它分成三块,去求容积,再用大正方形容积去减,但这太麻烦,如何更有成效地算出立方和呢?我再次从小点的数开始尝试计算。根据右表:

    edf367c832be7212ed28ff552a7db347.png

    d52b7ce636ffc861db86e623496bc09e.png

      1=1³,2+4+2=8=2³=(1+2+1)×2,3+6+9+6+3=27=3³=(1+2+3+2+1)×3,

      4+8+12+16+12+8+4=64=4³=(1+2+3+4+3+2+1)×4,……

    综上可知:1³+2³=(1+2)²=9, 猜想:a³+b³=(a+b)²,举例计算2³+3³=35≠(2+3)²,

    3³+4³≠(3+4)² ,a³+b³≠(a+b)²。

    通过进一步发现:2³+3³=35=36-1(1³),1³+2³+3³=(1+2+3)²,1³+2³+3³+4³=(1+2+3+4)²

    ……,得出:1³+2³+3³+4³+…n³=(1+2+3+4+…n)²,意外得出了连续自然数的立方和的计算方法。对于任意的两个数的立方和有没有规律呢?后来我查到了立方和公式:(a+b)×(a2-a×b+b2),这公式可真有意思,我试着去理解,似乎有一点头绪,但不清楚。我先去想,a+b=两数之和,a×b=以a为长b为宽的长方形,a2+b2是两数的平方之和,然而为什么要变成公式(a+b)×(a2-a×b+b2)呢?有待于我继续研究。

    告一段落——收获和体会最终我还是没有理解立方和公式,那么,在以后的人生中,我一定会尽自己的努力去理解它。因为随着年龄的长大,知识的积累,我懂的将会越来越多,我才能深入理解立方和公式。虽然我失败了,但我知道了示意图,也知道了立方和公式,就这样,我也收获了不少,我感悟道:“失败也美丽”!通过本次探索与发现,我知道了平方数的关联,巧求平方差、和,巧求立方差、和,我还学会用画图、列表来论证结果。在这次学习中,我由刚开始的找规律,然后根据规律去摸索原因,发现新公式,到后来的进攻立方数,一路艰辛。反思确实重要,要获得最终真谛,要知道哪些不足,必须通过反思。通过反思,会发现其中规律,获得规律后,要举一反三,才能有所突破,让下次做得更快更好。真可谓:“众里寻她千百度,蓦然回首,那人却在灯火阑珊处!”从中我发现了追求科学的真谛:数学要善于挑战自我,挑战的过程更要仔细观察、认真思考、多多比较。这样,才能英勇夺冠。数学数学,莫非就是数的科学。画图列表,莫非就是帮你思考。论证拓展,莫非就是一种挑战。从点动成线,到线动成面,我走近它;从蝴蝶模型,到π的终值,我研究它;从二维平方,到三维立方,我深入它;从勾股定理,到排列组合,我深深地爱上它!它,就是神奇的数学!!! 

    c7130f972d9ff898fc473d6a2f3169ac.png

    让孩子从小开始喜欢数学阅读

    陪伴孩子慢慢阅读属于自己的快乐有趣

    慢慢欣赏  慢慢成长

    765fc98f42b6341f5686ca1c78c12fd6.gif 765fc98f42b6341f5686ca1c78c12fd6.gif 765fc98f42b6341f5686ca1c78c12fd6.gifd51e867e30556f6c6b462c7bc966bfba.png
    展开全文
  • 更多精彩视频内容,请移步我们『芯知识学堂』的B站:原文作者:自成一派123转载来源:C语言与CPP编程(ID:cwdushu)时间、空间复杂度比较1 顺序查找算法思路:对于任意个序列,从一端开始,顺序扫描,依次将扫描到...

    c446b02554ff68ce43714b2f032dedfb.png

    温馨提示

    公众号菜单->获取资源->资料获取百万份学习资料任你下载!更多精彩视频内容,请移步我们『芯知识学堂』B站

    4881aed9cd0d77f6d0201703dd206306.png

    原文作者:自成一派123转载来源:C语言与CPP编程(ID:cwdushu)

    时间、空间复杂度比较

    a3edb6cd23c9dada419eda4dcd6152a4.png

    1 顺序查找

    算法思路

    对于任意一个序列,从一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。

    代码

    #include 
    #include
    #define keyType int
    //2020.05.24
    typedef struct
    {
    keyType key;//查找表中每个数据元素的值
    }ElemType;
    typedef struct
    {
    ElemType *elem;//存放查找表中数据元素的数组
    int length;//记录查找表中数据的总数量
    }SSTable;
    //创建查询数据
    void Create(SSTable **st,int length)
    {
    (*st)=(SSTable*)malloc(sizeof(SSTable));
    (*st)->length=length;
    (*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
    printf("输入表中的数据元素:\n");
    //根据查找表中数据元素的总长度,在存储时,从数组下标为 1 的空间开始存储数据
    for (int i=1; i<=length; i++)
    {
    scanf("%d",&((*st)->elem[i].key));
    }
    }
    //顺序查找函数,其中key为要查找的元素
    int Search_seq(SSTable *str,keyType key)
    {
    //str->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置,起监视哨的作用
    int len = str->length;
    //从最后一个数据元素依次遍历,一直遍历到数组下标为0
    for(int i=1; i {
    if(str->elem[i].key == key)
    {
    return i;
    }
    }
    //如果 i=0,说明查找失败;查找成功返回要查找元素key的位置i
    return 0;
    }
    int main()
    {
    SSTable *str;
    int num;
    printf("请输入创建数据元素的个数:\n");
    scanf("%d",&num);
    Create(&str, num);
    getchar();
    printf("请输入要查找的数据:\n");
    int key;
    scanf("%d",&key);
    int location=Search_seq(str, key);
    if (location==0) {
    printf("查找失败");
    }else{
    printf("要查找的%d的顺序为:%d",key,location);
    }
    return 0;
    }

    运行结果

    e75f45ae194c7459bc72334716429bee.png
    查找成功
    2253d3af7f609816b58aa73918ed594b.png
    查找失败

    2 二分查找(折半查找)

    算法思路
    1. 确定查找范围low=0,high=N-1,计算中项mid=(low+high)/2。
    2. 若mid==x或low>=high,则结束查找;否则,向下继续。
    3. 若amidx,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给higt,并重新计算mid,转去执行步骤2。
    说明
    • 查找元素必须是有序的,如果是无序的则要先进行排序操作。
    • 在做查找的过程中,如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间,即求得 mid 的位置不是整数,需要统一做取整操作。

    折半查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,那就不建议使用。

                             ——《大话数据结构》

    代码

    #include 
    #include
    #define keyType int
    typedef struct
    {
    keyType key;//查找表中每个数据元素的值
    }ElemType;
    typedef struct
    {
    ElemType *elem;//存放查找表中数据元素的数组
    int length;//记录查找表中数据的总数量
    }SSTable;
    //创建查询数据
    void Create(SSTable **st,int length)
    {
    (*st)=(SSTable*)malloc(sizeof(SSTable));
    (*st)->length=length;
    (*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
    printf("输入表中的数据元素:\n");
    //根据查找表中数据元素的总长度,在存储时,从数组下标为 1 的空间开始存储数据
    for (int i=1; i<=length; i++)
    {
    scanf("%d",&((*st)->elem[i].key));
    }
    }
    //折半查找函数 key为要查找的元素
    int Search_Bin(SSTable *str,keyType key)
    {
    int low=1;//初始状态 low 指针指向第一个关键字
    int high=str->length;//high 指向最后一个关键字
    int mid;
    while (low<=high)
    {
    mid=(low+high)/2;//int 本身为整形,所以,mid 每次为取整的整数
    if(str->elem[mid].key==key)//如果 mid 指向的同要查找的相等,返回 mid 所指向的位置
    {
    return mid;
    }
    else if(str->elem[mid].key>key)//如果mid指向的关键字较大,则更新 high 指针的位置
    {
    high=mid-1;
    }
    //反之,则更新 low 指针的位置
    else
    {
    low=mid+1;
    }
    }
    return 0;
    }
    int main()
    {
    SSTable *str;
    int num;
    printf("请输入创建数据元素的个数:\n");
    scanf("%d",&num);
    Create(&str, num);
    getchar();
    printf("请输入要查找的数据:\n");
    int key;
    scanf("%d",&key);
    int location=Search_Bin(str, key);
    if (location==0) {
    printf("没有查找到");
    }else{
    printf("要查找的%d的顺序为:%d",key,location);
    }
    return 0;
    }

    运行结果

    402ee4ad9f8441f27c3d0b2dcde2e4ae.png
    查找成功
    8f50a21fd7e964c4eb013ce304efe007.png
    没有查找到

    3 插值查找

    插值查找基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找算法思路
    1. 确定查找范围low=0,high=N-1,计算中项mid=low+(key-a[low])/(a[high]-a[low])*(high-low)。
    2. 若mid==x或low>=high,则结束查找;否则,向下继续。
    3. 若amidx,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给higt,并重新计算mid,转去执行步骤2。
    说明
    • 插值查找是基于折半查找进行了优化的查找方法。
    • 当表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能要比折半查找要好得多。
    代码
    #include
    int array[10] = { 1, 4, 9, 16, 27, 31, 33, 35, 45, 64 };
    int InsertionSearch(int data)
    {
    int low = 0;
    int high = 10 - 1;
    int mid = -1;
    int comparisons = 1;
    int index = -1;
    while(low <= high)
    {
    printf("比较 %d 次\n" , comparisons );
    printf("low : %d, list[%d] = %d\n", low, low, array[low]);
    printf("high : %d, list[%d] = %d\n", high, high, array[high]);
    comparisons++;
    mid = low + (((double)(high - low) / (array[high] - array[low])) * (data - array[low]));
    printf("mid = %d\n",mid);
    // 没有找到
    if(array[mid] == data)
    {
    index = mid;
    break;
    }
    else
    {
    if(array[mid] < data)
    {
    low = mid + 1;
    }
    else
    {
    high = mid - 1;
    }
    }
    }
    printf("比较次数: %d\n", --comparisons);
    return index;
    }
    int main()
    {
    int location = InsertionSearch(27); //测试代,查27,可以找到
    if(location != -1)
    {
    printf("查找元素顺序为: %d\n" ,(location+1));
    }
    else
    {
    printf("没有查找到");
    }
    return 0;
    }

    运行结果

    2746e53bfa85431a3af00913cf25711c.png
    运行结果

    4 斐波那契查找

    斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,及n=F(k)-1;开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1).算法思路
    1. 相等,mid位置的元素即为所求
    2. 大于,low=mid+1,k-=2;
    3. 小于,high=mid-1,k-=1。
    说明low=mid+1说明待查找的元素在[mid+1,high]范围内,k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个,所以可以递归的应用斐波那契查找。

    代码

    #include "stdafx.h"
    #include
    #include
    using namespace std;
    const int max_size=20;//斐波那契数组的长度
    /*构造一个斐波那契数组*/
    void Fibonacci(int * F)
    {
    F[0]=0;
    F[1]=1;
    for(int i=2;i F[i]=F[i-1]+F[i-2];
    }
    /*定义斐波那契查找法*/
    int FibonacciSearch(int *a, int n, int key) //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
    {
    int low=0;
    int high=n-1;
    int F[max_size];
    Fibonacci(F);//构造一个斐波那契数组F
    int k=0;
    while(n>F[k]-1)//计算n位于斐波那契数列的位置
    ++k;
    int * temp;//将数组a扩展到F[k]-1的长度
    temp=new int [F[k]-1];
    memcpy(temp,a,n*sizeof(int));
    for(int i=n;i temp[i]=a[n-1];
    while(low<=high)
    {
    int mid=low+F[k-1]-1;
    if(key {
    high=mid-1;
    k-=1;
    }
    else if(key>temp[mid])
    {
    low=mid+1;
    k-=2;
    }
    else
    {
    if(mid return mid; //若相等则说明mid即为查找到的位置
    else
    return n-1; //若mid>=n则说明是扩展的数值,返回n-1
    }
    }
    delete [] temp;
    return 0;
    }
    int main()
    {
    int a[] = {0,1,4,35,47,53,62,78,88,99};
    int key=47;
    int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
    if(index == 0)
    {
    cout< }
    else
    {
    cout< }
    return 0;
    }

    运行结果

    bb1ec8f4db24571bc531ac9dca5a162b.png
    47的位置为5

    5 哈希查找

    哈希表我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素"分类",然后将这个元素存储在相应"类"所对应的地方。但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。"直接定址"与"解决冲突"是哈希表的两大特点。哈希函数规则:通过某种转换关系,使关键字适度的分散到指定大小的的顺序结构中,越分散,则以后查找的时间复杂度越小,空间复杂度越高。算法思路如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。
    1. 用给定的哈希函数构造哈希表;
    2. 根据选择的冲突处理方法(常见方法:拉链法和线性探测法)解决地址冲突;
    3. 在哈希表的基础上执行哈希查找;

    代码

    #include
    #include
    #define SUCCESS 1
    #define UNSUCCESS 0
    #define OVERFLOW -1
    #define OK 1
    #define ERROR -1
    #define MAXNUM 9999 // 用于初始化哈希表的记录 key
    typedef int Status;
    typedef int KeyType;
    // 哈希表中的记录类型
    typedef struct
    {
    KeyType key;
    }RcdType;
    // 哈希表类型
    typedef struct
    {
    RcdType *rcd;
    int size;
    int count;
    int *tag;
    }HashTable;
    // 哈希表每次重建增长后的大小
    int hashsize[] = { 11, 31, 61, 127, 251, 503 };
    int index = 0;
    // 初始哈希表
    Status InitHashTable(HashTable &H, int size)
    {
    int i;
    H.rcd = (RcdType *)malloc(sizeof(RcdType)*size);
    H.tag = (int *)malloc(sizeof(int)*size);
    if (NULL == H.rcd || NULL == H.tag) return OVERFLOW;
    KeyType maxNum = MAXNUM;
    for (i = 0; i < size; i++)
    {
    H.tag[i] = 0;
    H.rcd[i].key = maxNum;
    }
    H.size = size;
    H.count = 0;
    return OK;
    }
    // 哈希函数:除留余数法
    int Hash(KeyType key, int m)
    {
    return (3 * key) % m;
    }
    // 处理哈希冲突:线性探测
    void collision(int &p, int m)
    {
    p = (p + 1) % m;
    }
    // 在哈希表中查询
    Status SearchHash(HashTable H, KeyType key, int &p, int &c)
    {
    p = Hash(key, H.size);
    int h = p;
    c = 0;
    while ((1 == H.tag[p] && H.rcd[p].key != key) || -1 == H.tag[p])
    {
    collision(p, H.size); c++;
    }
    if (1 == H.tag[p] && key == H.rcd[p].key) return SUCCESS;
    else return UNSUCCESS;
    }
    //打印哈希表
    void printHash(HashTable H)
    {
    int i;
    printf("key : ");
    for (i = 0; i < H.size; i++)
    printf("%3d ", H.rcd[i].key);
    printf("\n");
    printf("tag : ");
    for (i = 0; i < H.size; i++)
    printf("%3d ", H.tag[i]);
    printf("\n\n");
    }
    // 函数声明:插入哈希表
    Status InsertHash(HashTable &H, KeyType key);
    // 重建哈希表
    Status recreateHash(HashTable &H)
    {
    RcdType *orcd;
    int *otag, osize, i;
    orcd = H.rcd;
    otag = H.tag;
    osize = H.size;
    InitHashTable(H, hashsize[index++]);
    //把所有元素,按照新哈希函数放到新表中
    for (i = 0; i < osize; i++)
    {
    if (1 == otag[i])
    {
    InsertHash(H, orcd[i].key);
    }
    }
    return OK;
    }
    // 插入哈希表
    Status InsertHash(HashTable &H, KeyType key)
    {
    int p, c;
    if (UNSUCCESS == SearchHash(H, key, p, c))
    { //没有相同key
    if (c*1.0 / H.size < 0.5)
    { //冲突次数未达到上线
    //插入代码
    H.rcd[p].key = key;
    H.tag[p] = 1;
    H.count++;
    return SUCCESS;
    }
    else recreateHash(H); //重构哈希表
    }
    return UNSUCCESS;
    }
    // 删除哈希表
    Status DeleteHash(HashTable &H, KeyType key)
    {
    int p, c;
    if (SUCCESS == SearchHash(H, key, p, c))
    {
    //删除代码
    H.tag[p] = -1;
    H.count--;
    return SUCCESS;
    }
    else return UNSUCCESS;
    }
    int main()
    {
    printf("-----哈希表-----\n");
    HashTable H;
    int i;
    int size = 11;
    KeyType array[8] = { 22, 41, 53, 46, 30, 13, 12, 67 };
    KeyType key;
    //初始化哈希表
    printf("初始化哈希表\n");
    if (SUCCESS == InitHashTable(H, hashsize[index++])) printf("初始化成功\n");
    //插入哈希表
    printf("插入哈希表\n");
    for (i = 0; i <= 7; i++)
    {
    key = array[i];
    InsertHash(H, key);
    printHash(H);
    }
    //删除哈希表
    printf("删除哈希表中key为12的元素\n");
    int p, c;
    if (SUCCESS == DeleteHash(H, 12))
    {
    printf("删除成功,此时哈希表为:\n");
    printHash(H);
    }
    //查询哈希表
    printf("查询哈希表中key为67的元素\n");
    if (SUCCESS == SearchHash(H, 67, p, c)) printf("查询成功\n");
    //再次插入,测试哈希表的重建
    printf("再次插入,测试哈希表的重建:\n");
    KeyType array1[8] = { 27, 47, 57, 47, 37, 17, 93, 67 };
    for (i = 0; i <= 7; i++)
    {
    key = array1[i];
    InsertHash(H, key);
    printHash(H);
    }
    getchar();
    return 0;
    }

    6 二叉树查找

    二叉查找树是先对待查找的数据进行生成树,确保树的左分支的值小于右分支的值,然后在就行和每个节点的父节点比较大小,查找最适合的范围。这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。算法思路
    1. 若b是空树,则搜索失败:
    2. 若x等于b的根节点的数据域之值,则查找成功:
    3. 若x小于b的根节点的数据域之值,则搜索左子树:
    4. 查找右子树。
    代码递归和非递归
    //非递归查找算法
    BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p)
    {
    //查找函数返回指向关键字值为key的结点指针,不存在则返回NULL
    p=NULL;
    while(T!=NULL&&key!=T->data)
    {
    p=T; //指向被查找结点的双亲
    if(keydata)
    T=T->lchild; //查找左子树
    else
    T=T->rchild; //查找右子树
    }
    return T;
    }
    //递归算法
    Status Search_BST(BiTree T, int key, BiTree f, BiTree *p)
    {
    //查找BST中是否存在key,f指向T双亲,其初始值为NULL
    //若查找成功,指针p指向数据元素结点,返回true;
    //若失败,p指向查找路径上访问的最后一个结点并返回false
    if(!T)
    {
    *p=f;
    return false;
    }
    else if(key==T->data)
    { //查找成功
    *p=T;
    return true;
    }
    else if(keydata)
    return Search_BST(T->lchild,key,T,p); //递归查找左子树
    else
    return Search_BST(T->rchild,key,T,p); //递归查找右子树
    }

    7 2-3树

    2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node),他保存1个key和左右两个自己点。对应3节点(3-node),保存两个Key,2-3查找树的定义如下:
    1. 要么为空,要么:
    2. 对于2节点,该节点保存一个key及对应value,以及两个指向左右节点的节点,左节点也是一个2-3节点,所有的值都比key要小,右节点也是一个2-3节点,所有的值比key要大。
    3. 对于3节点,该节点保存两个key及对应value,以及三个指向左中右的节点。左节点也是一个2-3节点,所有的值均比两个key中的最小的key还要小;中间节点也是一个2-3节点,中间节点的key值在两个跟节点key值之间;右节点也是一个2-3节点,节点的所有key值比两个key中的最大的key还要大。
    f4612a6fda1c5efbea8048055aed3a98.png
    算法思路:要判断一个键是否在树中,我们先将它和根结点中的键比较。如果它和其中的任何一个相等,查找命中。否则我们就根据比较的结果找到指向相应区间的链接,并在其指向的子树中递归地继续查找。如果这是个空链接,查找未命中。
    e8266f2bf20d5f06671e183ae6e32c41.png2-3 树中查找键为H的节点
    b413974814fb4fa4cc5a7b77ba56fd5c.png2-3 树中查找键为B的节点

    代码

    two_three *search23(two_three *t, element x)
    {
    while(t)
    {
    if (x < t->data_l)
    {
    t = t->left_child;
    }
    else if (x > t->data_l && x < t->data_r)
    {
    t = t->middle_child;
    }
    else if (x > t->data_r)
    {
    t = t->right_child;
    }
    else
    {
    return t;
    }
    }
    return NULL;
    }

    8 红黑树

    2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgn,从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂,于是就有了一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree)。理解红黑树一句话就够了:红黑树就是用红链接表示3-结点的2-3树现在我们对2-3树进行改造,改造成一个二叉树。怎么改造呢?对于2节点,保持不变;对于3节点,我们首先将3节点中左侧的元素标记为红色,然后我们将其改造成图3的形式;再将3节点的位于中间的子节点的父节点设置为父节点中那个红色的节点,如图4的所示;最后我们将图4的形式改为二叉树的样子,如图5所示。图5是不是很熟悉,没错,这就是我们常常提到的大名鼎鼎的红黑树了。如下图所示。
    14c5908078b0e1c3059802051ecf4f46.png2-3树转红黑树
    为什么使用红黑树
    • 红黑树是一种平衡树,他复杂的定义和规则都是为了保证树的平衡性。如果树不保证他的平衡性就是下图:很显然这就变成一个链表了。
    • 保证平衡性的最大的目的就是降低树的高度,因为树的查找性能取决于树的高度。所以树的高度越低搜索的效率越高!
    • 这也是为什么存在二叉树、搜索二叉树等,各类树的目的。
    红黑树性质
    • 每个节点要么是黑色,要么是红色。
    • 根节点是黑色。
    • 每个叶子节点(NIL)是黑色。
    • 每个红色结点的两个子结点一定都是黑色。
    • 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
    算法思路红黑树的思想就是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的,使用红色链接的两个2-nodes来表示一个3-nodes节点,并且向左倾斜,即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改,和普通的二叉查找树相同代码
    #define BLACK 1
    #define RED 0
    #include
    using namespace std;
    class bst
    {
    private:
    struct Node
    {
    int value;
    bool color;
    Node *leftTree, *rightTree, *parent;
    Node() : value(0), color(RED), leftTree(NULL), rightTree(NULL), parent(NULL) { }
    Node* grandparent()
    {
    if (parent == NULL)
    {
    return NULL;
    }
    return parent->parent;
    }
    Node* uncle()
    {
    if (grandparent() == NULL)
    {
    return NULL;
    }
    if (parent == grandparent()->rightTree)
    return grandparent()->leftTree;
    else
    return grandparent()->rightTree;
    }
    Node* sibling()
    {
    if (parent->leftTree == this)
    return parent->rightTree;
    else
    return parent->leftTree;
    }
    };
    void rotate_right(Node *p)
    {
    Node *gp = p->grandparent();
    Node *fa = p->parent;
    Node *y = p->rightTree;
    fa->leftTree = y;
    if (y != NIL)
    y->parent = fa;
    p->rightTree = fa;
    fa->parent = p;
    if (root == fa)
    root = p;
    p->parent = gp;
    if (gp != NULL)
    {
    if (gp->leftTree == fa)
    gp->leftTree = p;
    else
    gp->rightTree = p;
    }
    }
    void rotate_left(Node *p)
    {
    if (p->parent == NULL)
    {
    root = p;
    return;
    }
    Node *gp = p->grandparent();
    Node *fa = p->parent;
    Node *y = p->leftTree;
    fa->rightTree = y;
    if (y != NIL)
    y->parent = fa;
    p->leftTree = fa;
    fa->parent = p;
    if (root == fa)
    root = p;
    p->parent = gp;
    if (gp != NULL)
    {
    if (gp->leftTree == fa)
    gp->leftTree = p;
    else
    gp->rightTree = p;
    }
    }
    void inorder(Node *p)
    {
    if (p == NIL)
    return;
    if (p->leftTree)
    inorder(p->leftTree);
    cout << p->value << " ";
    if (p->rightTree)
    inorder(p->rightTree);
    }
    string outputColor(bool color)
    {
    return color ? "BLACK" : "RED";
    }
    Node* getSmallestChild(Node *p)
    {
    if (p->leftTree == NIL)
    return p;
    return getSmallestChild(p->leftTree);
    }
    bool delete_child(Node *p, int data)
    {
    if (p->value > data)
    {
    if (p->leftTree == NIL)
    {
    return false;
    }
    return delete_child(p->leftTree, data);
    }
    else if (p->value < data)
    {
    if (p->rightTree == NIL)
    {
    return false;
    }
    return delete_child(p->rightTree, data);
    }
    else if (p->value == data)
    {
    if (p->rightTree == NIL)
    {
    delete_one_child(p);
    return true;
    }
    Node *smallest = getSmallestChild(p->rightTree);
    swap(p->value, smallest->value);
    delete_one_child(smallest);
    return true;
    }
    else
    {
    return false;
    }
    }
    void delete_one_child(Node *p)
    {
    Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
    if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL)
    {
    p = NULL;
    root = p;
    return;
    }
    if (p->parent == NULL)
    {
    delete p;
    child->parent = NULL;
    root = child;
    root->color = BLACK;
    return;
    }
    if (p->parent->leftTree == p)
    {
    p->parent->leftTree = child;
    }
    else
    {
    p->parent->rightTree = child;
    }
    child->parent = p->parent;
    if (p->color == BLACK)
    {
    if (child->color == RED)
    {
    child->color = BLACK;
    }
    else
    delete_case(child);
    }
    delete p;
    }
    void delete_case(Node *p)
    {
    if (p->parent == NULL)
    {
    p->color = BLACK;
    return;
    }
    if (p->sibling()->color == RED)
    {
    p->parent->color = RED;
    p->sibling()->color = BLACK;
    if (p == p->parent->leftTree)
    rotate_left(p->sibling());
    else
    rotate_right(p->sibling());
    }
    if (p->parent->color == BLACK && p->sibling()->color == BLACK
    && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK)
    {
    p->sibling()->color = RED;
    delete_case(p->parent);
    }
    else if (p->parent->color == RED && p->sibling()->color == BLACK
    && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK)
    {
    p->sibling()->color = RED;
    p->parent->color = BLACK;
    }
    else
    {
    if (p->sibling()->color == BLACK)
    {
    if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED
    && p->sibling()->rightTree->color == BLACK)
    {
    p->sibling()->color = RED;
    p->sibling()->leftTree->color = BLACK;
    rotate_right(p->sibling()->leftTree);
    }
    else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
    && p->sibling()->rightTree->color == RED)
    {
    p->sibling()->color = RED;
    p->sibling()->rightTree->color = BLACK;
    rotate_left(p->sibling()->rightTree);
    }
    }
    p->sibling()->color = p->parent->color;
    p->parent->color = BLACK;
    if (p == p->parent->leftTree)
    {
    p->sibling()->rightTree->color = BLACK;
    rotate_left(p->sibling());
    }
    else
    {
    p->sibling()->leftTree->color = BLACK;
    rotate_right(p->sibling());
    }
    }
    }
    void insert(Node *p, int data)
    {
    if (p->value >= data)
    {
    if (p->leftTree != NIL)
    insert(p->leftTree, data);
    else
    {
    Node *tmp = new Node();
    tmp->value = data;
    tmp->leftTree = tmp->rightTree = NIL;
    tmp->parent = p;
    p->leftTree = tmp;
    insert_case(tmp);
    }
    }
    else
    {
    if (p->rightTree != NIL)
    insert(p->rightTree, data);
    else
    {
    Node *tmp = new Node();
    tmp->value = data;
    tmp->leftTree = tmp->rightTree = NIL;
    tmp->parent = p;
    p->rightTree = tmp;
    insert_case(tmp);
    }
    }
    }
    void insert_case(Node *p)
    {
    if (p->parent == NULL)
    {
    root = p;
    p->color = BLACK;
    return;
    }
    if (p->parent->color == RED)
    {
    if (p->uncle()->color == RED)
    {
    p->parent->color = p->uncle()->color = BLACK;
    p->grandparent()->color = RED;
    insert_case(p->grandparent());
    }
    else
    {
    if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent)
    {
    rotate_left(p);
    rotate_right(p);
    p->color = BLACK;
    p->leftTree->color = p->rightTree->color = RED;
    }
    else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent)
    {
    rotate_right(p);
    rotate_left(p);
    p->color = BLACK;
    p->leftTree->color = p->rightTree->color = RED;
    }
    else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent)
    {
    p->parent->color = BLACK;
    p->grandparent()->color = RED;
    rotate_right(p->parent);
    }
    else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent)
    {
    p->parent->color = BLACK;
    p->grandparent()->color = RED;
    rotate_left(p->parent);
    }
    }
    }
    }
    void DeleteTree(Node *p)
    {
    if (!p || p == NIL)
    {
    return;
    }
    DeleteTree(p->leftTree);
    DeleteTree(p->rightTree);
    delete p;
    }
    public:
    bst()
    {
    NIL = new Node();
    NIL->color = BLACK;
    root = NULL;
    }
    ~bst()
    {
    if (root)
    DeleteTree(root);
    delete NIL;
    }
    void inorder()
    {
    if (root == NULL)
    return;
    inorder(root);
    cout << endl;
    }
    void insert(int x)
    {
    if (root == NULL)
    {
    root = new Node();
    root->color = BLACK;
    root->leftTree = root->rightTree = NIL;
    root->value = x;
    }
    else
    {
    insert(root, x);
    }
    }
    bool delete_value(int data)
    {
    return delete_child(root, data);
    }
    private:
    Node *root, *NIL;
    };
    int main()
    {
    cout << "---【红黑树】---" << endl;
    // 创建红黑树
    bst tree;
    // 插入元素
    tree.insert(2);
    tree.insert(9);
    tree.insert(-10);
    tree.insert(0);
    tree.insert(33);
    tree.insert(-19);
    // 顺序打印红黑树
    cout << "插入元素后的红黑树:" << endl;
    tree.inorder();
    // 删除元素
    tree.delete_value(2);
    // 顺序打印红黑树
    cout << "删除元素 2 后的红黑树:" << endl;
    tree.inorder();
    // 析构
    tree.~bst();
    getchar();
    return 0;
    }

    9 B树/B+树

    在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统。

                                 ——维基百科
    B 树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。
    • 定义任意非叶子结点最多只有M个儿子;且M>2;
    • 根结点的儿子数为[2, M];
    • 除根结点以外的非叶子结点的儿子数为[M/2, M];
    • 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
    • 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
    • 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的 子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
    • 所有叶子结点位于同一层;
    如:(M=3)fee88741da8cfba0fbf96492e5c66a84.png算法思路从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;
    • 关键字集合分布在整颗树中;
    • 任何一个关键字出现且只出现在一个结点中;
    • 搜索有可能在非叶子结点结束;
    • 其搜索性能等价于在关键字全集内做一次二分查找;
    • 自动层次控制;

    代码

    BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)
    {
    int i = 0;
    while (i < tree->keynum && key > tree->key[i])
    {
    ++i;
    }

    // 查找关键字
    if (i < tree->keynum && tree->key[i] == key)
    {
    *pos = i;
    return tree;
    }

    // tree 为叶子节点,找不到 key,查找失败返回
    if (tree->isLeaf)
    {
    return NULL;
    }

    // 节点内查找失败,但 tree->key[i - 1]< key < tree->key[i],
    // 下一个查找的结点应为 child[i]

    // 从磁盘读取第 i 个孩子的数据
    disk_read(&tree->child[i]);

    // 递归地继续查找于树 tree->child[i]
    return BTree_recursive_search(tree->child[i], key, pos);
    }
    B+树B+树是B树的变体,也是一种多路搜索树:其定义基本与B-树同,除了:
    • 非叶子结点的子树指针与关键字个数相同;
    • 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树, B树是开区间
    • 为所有叶子结点增加一个链指针;
    • 所有关键字都在叶子结点出现;
    如:(M=3)
    7b3f2dc22abd03751c4220deef559cbe.png1
    算法思路B+的搜索与B树也基本相同,区别是B+树只有达到叶子结点才命中(B树可以在 非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;
    • 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
    • 不可能在非叶子结点命中;
    • 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
    • 更适合文件索引系统;

    有你想看的精彩

    积分换购|额温枪开发板居然真的不要钱!

    没了美国EDA软件,我们就不能做芯片?

    什么?C/C++面试过不了?因为你还没看过这个!

    十大经典排序算法,你会几种?(附:动态演示+代码)

    STM8、STM32可以超频吗?

    5个IO口实现25个按键的扫描,他做到了!堪称一绝!

    技术总监:求求你,别写这么多if...else..了

    为什么将 0.1f 改为 0 会使性能降低 10 倍?

    b65512612effbc4d0707a0ecac502de4.gif

    知识改变命运『芯知识学堂』伴你前行 

    f60cc4c64fb10924e5e2af875d70212f.png

    长按关注我们,不错过每一篇好文

    fb3cfc415304894210ed21ad290c9898.gif4b7479c6fb679c401f80418a69a14d9a.png点个在看再走呗! 
    展开全文
  • 如果某个数 K 的平方乘以 N 以后,结果的末尾位数等于 K,那么就称这个数为“N-自守数”。例如 3×92​2​​=25392,而 25392 的末尾两位正好是 92,所以 92 是个 3-自守数。 本题就请你编写程序判断个给定的...

    题目:

    如果某个数 K 的平方乘以 N 以后,结果的末尾几位数等于 K,那么就称这个数为“N-自守数”。例如 3×92​2​​=25392,而 25392 的末尾两位正好是 92,所以 92 是一个 3-自守数。

    本题就请你编写程序判断一个给定的数字是否关于某个 N 是 N-自守数。

    输入格式:

    输入在第一行中给出正整数 M(≤20),随后一行给出 M 个待检测的、不超过 1000 的正整数。

    输出格式:

    对每个需要检测的数字,如果它是 N-自守数就在一行中输出最小的 N 和 NK​2​​ 的值,以一个空格隔开;否则输出 No。注意题目保证 N<10。

    输入样例:

    3
    92 5 233
    

     

    输出样例:

    3 25392
    1 25
    No

     

     

    思路:

     枚举,这里我使用了字符串的find方法

     

    代码:

    #include<iostream>
    #include<sstream>
    using namespace std;
    int main()
    {
        int num;
        cin>>num;
        for(int i=0;i<num;i++)
        {
            bool find_n=false;
            stringstream ss;
            string k_s="";
            int k;
            cin>>k;
            ss<<k;ss>>k_s;ss.clear();
            for(int j=1;j<10;j++)
            {
                int res;
                stringstream ss1;
                string res_s;
                res=j*k*k;
                ss1<<res;ss1>>res_s;ss1.clear();
                if(res_s.find(k_s,res_s.size()-k_s.size())!=-1)
                {
                    find_n=true;
                    cout<<j<<" "<<res<<endl;
                    break;
                }
            }
            if(!find_n)
                cout<<"No"<<endl;
        }
        return 0;
    }
    

     

    展开全文
  • 我们知道条直线可以把平面分成两部分,可以理解成这条直线的加入贡献了个新的部分(可能说的不严谨,指的是答案加1,因为初始状态是个整的平面) 若用ci[i]表示第i条加入的直线对答案的贡献 易知ci[1] = 1...
  • 的余数

    2019-07-14 07:24:08
    根据“个数被9除的余数,等于它各位数字之和被9除的余数”这“弃法”的原理,考虑本题的答案,只须考虑: A=1+2+3+4+5+6+7+8+9+1+0+1+1+……+1+9+8+9+1+9+9+0+1+9+9+1被9的余数,并将它与如下的B作比较: B=...
  • 届蓝桥杯 C++ B组

    2021-02-05 09:37:10
    题 第天 ans :125 使用excel,datedif函数计算 第二题 明码 ans:387420489(我是憨批,次方我给算成81了我日) 汉字解密出来为:次方等于多少 哈哈哈哈卧槽,本来咋都想不出来负数的二进制怎么...
  • 目录第章 马尔柯夫分析、马尔柯夫分析的数学原理二、马尔柯夫分析方法的步骤三、马尔柯夫分析方法的个结论四、马尔柯夫分析问题的要求 第章 马尔柯夫分析 、马尔柯夫分析的数学原理 对于由种情况转换至...
  • 35岁的不要,二十岁又拒绝,觉得现在很多中小型企业真的很“矫情”,出不起工资找经验丰富的人才,也不想给刚毕业大学生份适合的岗位。 这也是造成很多中小企业寿命只有3-5年的重要因素之,因为他们在用人方面...
  • 晚五的工作值得留恋吗?

    千次阅读 多人点赞 2019-12-19 11:40:00
    “虽然每个人的工作经历各有不同,而且每个人的故事也千变万化,但我认为有段朝晚五的工作经历实际上是件好事。” 作者 |Anna Grigoryan 译者 |弯月,责编 | 郭芮 出品 | CSDN(ID:CSDNnews) 以下为...
  • 章介绍了种典型ByteBuf的原理,这章介绍它的使用方法,包括Netty是如何使用ByteBuf的。 引用计数 上章已经提及“引用计数”的概念;引用及计数是种历史悠久的对象生命周期管理手段。它的核心理念是在...
  • 、简介流明(英文 Lumen),简写 lm,是光通量的国际单位。光通量 (luminous flux) 代表了我们人眼对不同波长的光的变化铭感度。我们一般说的投影仪流明指的是 ANSI流明,这个是国际公认的标准单位。在不同位置对...
  • 题2000年1月1日为该年的第天,那么2000年5月4日为该年的第天答案:125第二题给...字节31 字节32就是个转码的过程,直接原码就可以看出来是 次方等于多少?答案:387420489第三题有100个数,求它们的...
  • ~中外股市中90%的投资...设置停损点或止损位,就等于为你买的股票装个“保险丝”。如果股价大跌连跌,你却只会烧坏(损失)根“保险丝”(止损价)。我认为,个人是否可以做个证券投资者,其必备的基本素质不
  • 展开全部14-9=5 15-9=6 16-9=7方法du:点数法14根小棒或zhi小圆点去掉个,也就dao是每次专去个,去9次,还剩5个。属方法二:破十法14可以分成10和4,,4减9不够减,用10减9等于1,然后用4加1等于5。总结一下:先...
  • 中外股市中90%的投资者处于亏损状态,各有各的原因,典型的有以下种:、不及时止损。很多人不是不懂这个道理,就是心太软,下不了手。绝对要有停损点,因为你决不可能知道这只股票会跌多深。设置停损点或止损位...
  • 最后的这讲很多是介绍一些概念以及应用和复习总结,所以简单记录下一下,不再详细展开。 主要内容有: 马尔可夫矩阵以及傅里叶级数的概念 实对称矩阵以及正定矩阵的...每列元素的和都等于1 马尔可夫矩阵有两条...
  • 512. Decode Ways 有个消息包含A-Z通过以下规则编码 'A' -> 1 ...如果当前字符不等于0那么f[i]+=f[i-1],如果当前字符的前个字符不为0,并且两者加起来是小于26的,那么结果还要加上法f...
  • 求三角形内的点的个数为奇数的三角形数 官方解题...实在不知道有向面积怎么转换成无向的 交了十次依旧WA 在网上看到另种做法 感觉很好 利用叉乘算出每个线段下面的点 三角形是由三条线段所围成 所以用条减...
  • 娄川河站了出来,他对铺子大师抱拳,“无论莫师弟如何,我... 铺子大师沉默下来,他知道渡仙舰一旦回头,那就等于增添了倍的危险都不止。 战舰中有些沉闷,似乎都在等铺子大师做出决定。 足足过了十数个呼吸...
  • 如果p的值等于root或者q的值等于root,那么p和q的最近公共祖先是root; 如果p和q位于位于root的异侧,则p和q的最近公共祖先就是root; 如果p和q位于位于root的同侧,就从p和q所在的侧开始递归查找。 代码 # ...
  • 这道题难倒了瑛姑十年,被黄蓉下子就答出来了。 平面魔方的一般定义:将自然数 1 到 N2 排列 N 行 N 列的方阵,使每行、每列及两条主对角线上的 N 个数的和都等于 N(N2+1)/2,这样的方阵称为 N 阶幻方。 ...
  • 个正整数 n, 请问最少多少个完全平方数(比如1, 4, 9...)的和等于n。在线评测地址:LintCode 领扣样例 1:输入: 12 输出: 3 解释: 4 + 4 + 4样例 2:输入: 13 输出: 2 解释: 4 + 9【题解】做法1:算法:dp我们用f[i]...
  • 大致题意:给你个n*m的01矩阵,现在要让你每行和每列都去掉个数字,而且要求相邻两行之间去掉数字的位置的绝对值要小于等于k。现在问你删除之后的矩形最多有种。首先,我们行考虑,对于同一行,显然...
  • 题意:给个矩形,在矩形内部有很多射线,这些射线的起点不会碰到矩形边界,问这些射线把矩形分成了部分 题解:分成的区域数等于线段交点数加,推导还是看jls的题解把 单说求交点个数的问题,我的方法就是扫描...
  • 题意:给出n个数和s,保证有个唯一的子序列等于s,问是哪个数? 思路:注意到n最大为36,我们可以用折半搜索,把前n/2的和全部用map记下并哈希记下状态,再搜后n/2个,找到直接输出。注意有可能选的都是后n/2...
  • 题目链接 大意:现在有n个人,每个回合都有一对人成为朋友,让你在首回合开始前和每回合结束后输出选4个人,每个人都不是朋友的方案。...1.从所有大于等于2的组朋友选2个人,另外的随便选两个∑x≥2C(x2)∗C(...
  • 杨辉三角,是二项式系数在三角形中的种几何排列,中国南宋数学家杨辉1261年所著的《详解章算法》书中出现 特点 每个数等于它上方两数之和。 每行数字左右对称,由1开始逐渐变大。 第n行的数字有n项。 第n行...
  • 这个就不用说了,大家都明白,京豆等于1分钱,可在下单的时候兑换相应的金额。京豆的来源有很多方面,如购物返京豆、签到领京豆、浏览店铺领京豆、抽奖活动领京豆等等,除去购物返京豆,其他全部都领下来,天...

空空如也

空空如也

1 2 3 4 5 6
收藏数 108
精华内容 43
关键字:

一九等于几