美文网首页
数学趣题

数学趣题

作者: 情鬼下凡 | 来源:发表于2017-11-13 12:42 被阅读0次
  1. 格雷码
  • 定义:格雷码是一个数列集合,每个数使用二进制表示,每两个相邻的数之间只有一个位元的值不同,同时最后一个数与第一个数之间也只有一个位元值不同。
  • 性质:
    • 奇数项: 它与前一个格雷码相比只改动了最右边一个位元的值
    • 偶数项: 相对前一个格雷码只改变了从右数第一个1左边的一个位元的值
  1. 循环移动
  • 问题:给定长度为n的数组和数字i,将数组循环左移i位
  • 思路:根据i将原数组分为ab两部分,原问题就变为通过ab求ba,此时可以将a翻转,将b翻转,最后将数组整体翻转。这种方式时间与空间都消耗的较少。
  • 如:将数组0123456789循环左移3位
    • 数组分为a: 012 b: 3456789
    • ab分别翻转: 210 9876543
    • ab整体翻转: 3456789012
  1. 找出小于n的所有素数
  • 思路:从2开始,将1~n中所有2的倍数去除,3的倍数去除,直到根号n结束,剩下的数就是小于n的所有素数。
  1. 找出一个字符串中有重复的且长度最长的子字符串及其长度。

    1. 对与字符串按照子字符串长度从大到小递减的方式扫描
    2. 查找源字符串中是否有重复的子字符串,若有,就结束。没有就减小子字符串的长度并重复改步骤。
  2. 魔幻方阵

  • 定义: 一个n阶的幻方是一个由整数1、2、3……n^2组成的方阵,方阵的每行的整数和、每列上的整数和、及两条对角线中的每条整数和都等于同一个整数s,s被称为改幻方的幻和。
  • 杨辉斜排法(仅适用于n为奇数的情况)
    1. 将1放在第一行的中间,其余数按顺序、按以下规则放置
    2. 其余整数放在当前整数的斜右上方,其中有几种放置数的情况
      1. 若要放置的数处于第一行的上面,则将它置于最底行的对应列位置
      2. 若要放置的书在最右边一列的右侧,则将其放置于对应行的最左边一列。
      3. 若要放置的数字应放置的位置已经有数字放置,则将该数字置于上个放置好的数字的正下方。
  1. 寻找最大的n个数
  • 问题: 从一些各不相同的无序数中,找到最大的n个数
    • 直观想法: 利用快排对数据排序,然后取出最大的n个数,假设共有m个数,则时间复杂度为mlogm
      但是
    • 但若m很大,数据很多,无法一次全部都入到内存,则直接排序不再适用,此时可以考虑挑选数据集前n个数放入数组中,然后遍历升序的书,发现比数组n中最小的数大的数,就将数组中最小的数替换出来,找出n个数中最小的数可以使用小根堆,根节点的值最小,每次替换后需对数组排序,堆排序时间复杂度为logn,则总的时间复杂度为mlogn。
  1. 查找数组中的最大值和最小值
  • 直观想法: 遍历数组,同时与最大值、最小值作比较,一次遍历即可得到结果,这个过程中元素比较次数为2n
  • 优化解法
    1. 将数组元素两两分为一组,进行组内排序,小的放前面,大的放后面。这种操作在原始数组上进行,无需额外空间,此时比较n/2次
    2. 在原始数组下标为奇数的数据中找出最大值,此时比较n/2次
    3. 在原始数组下标为偶数的数据中找出最小值,此时比较n/2次
      这种方法总共比较了3n/2次,较2n次少
  1. 遍历一次单链表找到它的中间节点
    设置两个指针p和q,让p每次前进2个节点,q每次前进1个节点,当p走到终点时,q恰好在中间位置

  2. 判断单链表是否有环
    设置连个指针p和q,让p每次前进2个节点,q每次前进1个节点,这样如果存在环,p指针一定会与q指针相遇,若无环,则p指针必定会先成为null

  3. 判断两个链表是否相交
    若两个单链表相交,则他们相交节点之后的所有节点应该是两个链表共有的,所以最后一个节点必然相等,我们只要找到两个链表的尾节点,判断它们是否相等即可,这种思想的时间按复杂度为length(h1)+length(h2)

  4. 蜗牛爬杆问题

一根31cm长的细杆,2cm、7cm、12cm、17cm、25cm处各有一只蜗牛。开始时,蜗牛头朝做还是朝右是任意的,他们只会向前走或调头,但不会后退,当任意两只蜗牛碰头时,它们会同时调头走,但速度不变,每秒走0.5cm,计算蜗牛全部离开杆的最长时间和最短时间。

  • 思路:蜗牛相遇时,同时调头,速度不变,可理解为俩蜗牛“擦肩而过”,方向,速度都未变,此时蜗牛离开的最长时间按为处于2cm的那只蜗牛走到最右边的时间(31-2)/0.5=58s,蜗牛离开的最短时间为处于“中间”的那只走到离它最近的一边的时间(31-17)/0.5=28s

相关文章

  • 数学趣题

    格雷码 定义:格雷码是一个数列集合,每个数使用二进制表示,每两个相邻的数之间只有一个位元的值不同,同时最后一个数与...

  • 为什么要学习数学思维

    卓越数学思维的每个学习单元由五个板块组成: “走进乐园”以数学故事、数学名题、数学趣题引入,渗透数学史、数学文化,...

  • 【学生作品】好玩的数学

    主题:弘扬数学文化,感受数学魅力” 内容可包括:数学家的故事、数学名人名句、数学名题、数学趣题、脑筋急转弯、数学日...

  • 【搬运工】教学经验——“三个一”

    经验1:每课一趣 每节课都要有一道以上的趣味数学题,或数学游戏,或趣味数学故事。有时在课始讲,有时在课末讲,有时渗...

  • 暑期总结

    目前为止,我还有《红星照耀中国》的书评和英语趣配音、数学剩余的一点题没完成。 我觉得我在数学方面的突破最大,因为在...

  • 简单

    午饭时讨论上午做的数学竞赛题,孩子非常兴奋。理科爸爸想趁热打铁,网上搜来几道趣题,非要再和孩子讨论一番。 爸爸一念...

  • 一周流水账:2017年4月23日

    4月17日:久趣课一节;英语Dick Whittington;钢琴20分钟;中文阅读《凤凰社》;数学研讨4题。 4...

  • 两个几乎相同的数列

    以后会在文集 "数学分享" 持续分享一些来自于微博或者其他网络来源的数学小趣题或者小知识。 下列两个数列非常有意思...

  • 趣题

    食淡身亦畅,语善行也端, 心宽胆则壮,识广气自芳。

  • 一周流水帐:2017年5月21日

    5月15日星期一:久趣课18:40,20:00两节;钢琴练习;幻想数学大战;数学题一道。 5月16日星期二:周记1...

网友评论

      本文标题:数学趣题

      本文链接:https://www.haomeiwen.com/subject/cmiamxtx.html