刘新宇

  • 关注
  • 短消息
  • 送银子
文章
11
评论
7
推荐
1
收藏
0
社区会龄
3 年
个人网站
--
个人简介

《算法新解》作者

  • 刘新宇 12推荐

    同构——编程中的数学

    我讲一个从马爷爷那里听来的故事。有一年春节的时候,北京地坛公园的庙会里人山人海,小朋友们拿着压岁钱在各种摊位上买自己喜欢的玩具。有一个摊位上围了一群人。地上一字排开摆了九个小玩具,每个玩具上依次贴着一元、二元、三元……直到九元的标签。摊主一边向大家吆喝,一边讲解游戏规则:“大家…...

  • 刘新宇 10推荐

    2019年读完的书

    这是连续第三年分享书单了。按照惯例每本书都列出读完的日期、作者、译者,链接、出版社、出版年、ISBN号。 今年破例我给出一些书的短评,并附有图片。 1. 2月3日,[法] 昂利 彭加勒(庞加莱),李醒民 译,《[科学与假设][1]》,商务印书馆,2006-8,ISBN: 97…...

  • 刘新宇 9推荐

    最小可用Id的命令式解法

    在《算法新解》的前言中,我们只给出了使用分而治之策略的线性时间O(n),常数空间O(1)的解法。这里我们给出另外两种命令式解法,它们都可以达到同样的性能。 首先我们先回顾一下书中讨论的一个重要性质 1 <= answer <= n + 1 其中n是序列的长度,…...

  • 刘新宇 8推荐

    寻找被篡改的数

    这一趣题和《算法新解》前言中的“最小可用Id”问题具有很多类似的地方。 有个从1到n的数字列表,经过某些处理后,发生了两点变化。1)序列的顺序被打乱了;2)其中一个数字x被篡改成了数字y,其中x和y都在1到n之间。能否找到一个线性时间,常数空间的方法,找出丢失的x和重复的y呢…...

  • 刘新宇 8推荐

    2018书单

    2018年读过的25本书: [法] 让-皮埃尔·卢米涅 马克·拉雪茨-雷 著 孙展 译《从无穷开始 科学的困惑与疆界》人民邮电出版社。12月读完。这本书的内容很好,但是第二章数学部分的翻译瑕疵较多。仍不失为一本好书; 丰子恺《少年音乐故事》海豚出版社。12月读完。关于乐理的…...

  • 刘新宇 7推荐

    2017年读完的书

    开列一下2017年读完的书 春日真人《庞加莱猜想,追寻宇宙的形状》图灵 远山启《数学与生活》图灵 谈祥柏《数学营养菜》中国少年儿童出版社 韩雪涛《数学悖论与三次数学危机》图灵 塞德里克 维拉尼《一个定理的诞生,我与菲尔兹奖的一千个日夜》图灵 尼尔森《数学写真集》1,2,3册…...

  • 刘新宇 7推荐

    同构——用数论指纹寻找子串排列

    有一道编程趣题, 要求判断一段文字T中,是否包含一个字符串W的某种排列。 据说不少公司还用这道题目用来面试程序员。题目的答案在网络上也到处都能搜索到。这道题目存在一个特别优雅的解法,体现了数学同构的优美。 数论中的算术基本定理说:任何一个正整数都可以唯一地表示成若干素…...

  • 刘新宇 5推荐

    用洛书幻方对抗人类玩家的井字棋程序

    我们在[此前的文章][1]中,给出了一个练习题: 编程实现一个井字棋游戏是传统人工智能中的经典问题,而计算机可以轻松算出三个数字的和并判断其是否等于15。请利用这个同构编写一个简化的井字棋程序,并做到不被人类玩家击败。 现在我们给出这道题目的参考答案。我们的思路是使用《…...

  • 刘新宇 3推荐

    同构——分红包问题

    这是一道小学三年级上学期,数学广角中关于搭配的题目。大意说,高个子舅舅春节回家,想给三个可爱的孩子小明、小强、小红一些红包用来买过年的玩具。他准备了6个红包,每个里面10元钱。每个小朋友肯定能得到红包,但不一定均分。问一共有几种发的方法。 这道题目如果编程暴力穷举的话会非常容…...

  • 刘新宇 3推荐

    同构——费马小定理

    费马小定理 费马小定理是法国数学家费马于1636年发现的。他在1640年10月18日写给友人法国数学家贝西(Bernard Frénicle de Bessy)的信中首次提出了这个定理。1736年,欧拉给出了费马小定理的一个证明。但从莱布尼茨未发表的手稿中发现他在1683年…...

  • 刘新宇 2推荐

    枚举组合

    枚举从n个元素中选取k个元素的所有组合 在《算法新解》一书的附录中(第529-530页),我们给出了如何从n个元素中选取k个元素进行排列的方法。和排列不同,组合并不关心元素间的先后顺序。记n个元素的列表为:{x1 , x2 , ..., xn}。从第一个元素x1开始,我们有两…...