实战比赛详解
实战比赛 ❶ 解说
挑战 18
实践竞赛（一）是一个团队的三人合作解决1道不同分数的数学和信息相关问题，并在3分钟的时限内争夺从正确问题中获得的总分的比赛。另外，在初步资料中写到，大约18%的问题不经过程序计算是无法回答的。
这个竞赛的内容类似于一个叫做竞争性编程的编程竞赛，它准确地描述了一个满足给定要求的程序，其中很多问题都需要计算机科学和数学知识，这是一个特点。
编程竞赛在国内外均有举办，有AtCoder、Topcoder、ACM国际大学生程序设计大赛等众多知名赛事。特别是，有一个叫做 Project Euler 的竞赛就非常接近这种格式。比赛提出了具有挑战性的数学/计算机程序问题，需要的不仅仅是数学洞察力。
此外，数学知识可以简单有效地解决问题，但在许多情况下，需要计算机和编程技能。
[质数]的问题是在打印一定范围的质数时，打印了多少次“1”。如果范围小，写在纸上算出来比直接写程序要快，但是如果范围大，怎么求素数就很重要了。众所周知的方法是“Eratosthenes筛”。
[竹内函数] 是一个递归定义的函数，用于对编程语言处理系统等进行基准测试，由竹内郁夫于 1974 年构思。递归定义的函数包括斐波那契数列和阿克曼函数。
[binary system]的问题是将二进制表示的数字重新表示为十进制的问题。你可以尽力写一个程序并要求它，也可以用计算机代替计算器来解决它。它也可以手工计算，但也可以用一点点巧妙的方式高效、轻松地计算出来。这是一个有趣的问题，可以通过各种方法解决。
[求和的序列]的问题是划分自然数的问题。对于一个自然数n，用自然数之和表示不计阶数差异的方法数称为除法数，p(n)，将不同自然数除法的方法数称为数不同的除法q（用n表示），把一个自然数n除为奇数个自然数的方法的个数称为奇数除法。这时候Q1是求q(50)的问题，Q2是求p(50)的问题。另外，Q3与来自“欧拉除法等式”的q(50)具有相同的值，即不同除法的数量和奇数除法的数量相等。
[divisor]的问题是除数函数
这是一个问题。特别地，它可以表示为 σ₀ (n) = d (n) 和 σ₁ (n) = σ (n)。 获得d(n)和σ(n)的具体方法是已知的，并且
反对
将会。顺便说一句，σ (n) = 2n 时的 n 被称为完全数，σ (n) = kn 时的 n 被称为 k 次完全数。换句话说，一个完全数可以看作是一个双重完全数。
[substring]的问题是一个与子集思想有关的问题。所有不同字符的长度为n的字符串的子串从幂集的思想可以有2n个子串。如果字符不是全部不同，考虑用同样的方法得到的2 n 个集合的并集，可以去掉重复的部分，得到所需字符串的集合。在这种情况下，由于 n = 11 很小，即使从 2048 中去除重叠部分也可以在现实的时间内求解，但是如果 n 很大，则动态规划方法是现实的。..
为了解释重要的部分，假设创建了一个使用从第一个字符到第 k 个字符的字符的子串。找出这些子串的并集加上末尾的第 k+1 个字符，并将其用作使用从第一个字符到第 k+1 个字符的字符的子串。此后，重复此方法。
[整数]问题是通过编程遇到数论中未解决的问题，如出租车数、科拉兹猜想、哥德巴赫猜想等问题。以下是与这些问题相关的一些事情。
• 以下命题被称为出租车号码问题的扩展。 “对于所有自然数 N，存在一个整数 m3，其中至少有 N 个整流点，其中三次曲线 x³ + y³ = m 对 x 和 y 都是正的。”
• Collatz 猜想问题与开头看到的“Takuchi 函数”问题类似，都是求递归运算次数的问题。另外，在2011年中考中，数学II/B的第6题是数值计算与计算机主题的题，与这道题相同的题是著名的科拉茨猜想题。
• 当您想到哥德巴赫猜想时，您通常会想到这样的想法，即大于全部 2 的偶数可以表示为两个素数之和。这个猜想的名字来自于哥德巴赫在 2 年的猜想，指出“任何大于 1742 的自然数都可以用三个素数之和来表示”。类似的猜想包括“弱哥德巴赫猜想”“大于5的奇数可以用三个质数之和表示”和“强金”“大于3的偶数可以用两个奇素数之和表示”。巴赫猜想。”
[Doremi cipher]的问题是一个与双字符替换密码相关的问题。问题1是分析实际解码所需密文的结构问题，问题2是实际创建替换表并在此基础上进行编码的问题。替代密码可能会出现在小说中，著名的有埃德加·爱伦·坡的《金虫》、江户川乱步的《二仙铜币》和亚瑟·柯南·道尔的福尔摩斯系列跳舞娃娃……
【字符串操作】的问题是函数操作字符串的顺序问题。在编程中，需要字符串、数组等运算和分析技术，是让你思考如何实际执行运算以获得想要的结果的问题。
【序列运算】的问题是与数组运算和递推公式相关的问题。如果 n 像问题 1 一样小，可以手工计算。关于问题2，实际上很难写出sn，但由于可以制定tn的递推公式，如果达到那个点，可以手动计算。
正如《竞赛指南》中的竞赛目的所述，在社会上，为了解决科学技术问题，往往使用计算机进行复杂的计算。此外，科学、数学、信息等各种事物在熟悉的科学现象中错综复杂地交织在一起，编程往往解决科学技术问题。这个问题是一个很好的问题，让我感受到了编程解决问题的用处和数学思维的需要。
Koichi Nakagawa，埼玉大学理工科研究生院
