这一题虽然是三级第一道编程题但实际上它是一道最经典的映射Mapping问题也是以后学习数组映射、哈希表、字符替换、密码替换等知识的重要基础。 GESP三级 编程题第一题《密码王国——数字加密大冒险》一、故事开始——神奇的密码本1、很久很久以前在数字王国里。1有一天国王宣布从今天开始所有数字都不能直接传送2为什么因为坏人会偷看。3于是国王发明了一本神奇的——《数字密码本》2、里面写着0 → 9 1 → 0 2 → 1 3 → 2 4 → 3 5 → 4 6 → 5 7 → 6 8 → 7 9 → 83、意思就是看到0就写成9。看到1就写成0。看到2就写成1。……每个数字都有一个新的身份。二、题目到底让我们干什么1、假设输入7表示有7个数字。2、然后输入0 2 0 3 4 1 9最后输入密码本9 0 1 2 3 4 5 6 7 83、题目要求把原来的数字全部变成新的数字。三、我们一起手工模拟1、原来的数字0查密码本0→9所以变成92、第二个数字2查密码本2→1得到13、第三个0还是94、第四个3变成25、继续4→3 1→0 9→86、最后得到9 1 9 2 3 0 8是不是和样例完全一样四、密码本其实就是一个数组1、来看密码本9 0 1 2 3 4 5 6 7 82、我们把它放进数组。keys[]里面。数组的编号索引就是数字。下标索引 0 1 2 3 4 5 6 7 8 9数组里面放的是9 0 1 2 3 4 5 6 7 8画出来就是数字 0 ─────► 9 1 ─────► 0 2 ─────► 1 3 ─────► 2 4 ─────► 3 5 ─────► 4 6 ─────► 5 7 ─────► 6 8 ─────► 7 9 ─────► 8是不是特别像一本密码本3、数组下标就是原来的数字1例如keys[0]得到9表示0→92如果keys[4]得到3表示4→33直接keys[数字]就能找到答案。4这就是数组映射这是特别重要的思想五、程序是怎么工作的汉克老师带大家一步一步运行。1、第一步输入7程序知道共有7个数字2、第二步输入0 2 0 3 4 1 9存进a[]里面。3、现在a ↓ 0 2 0 3 4 1 94、第三步1输入密码本9 0 1 2 3 4 5 6 7 82存进keys[]里面。3现在keys ↓ 9 0 1 2 3 4 5 6 7 85、第四步开始一个一个输出。1第一次a[0]里面是0于是keys[a[0]] ↓ keys[0] ↓ 9输出92第二次a[1] 2于是keys[2] 1输出13第三次a[2] 0得到keys[0] 9输出9……一直到最后。6、整个过程就是原数字 ↓ 作为数组下标 ↓ 查密码本 ↓ 输出新数字是不是特别简单七、完整代码#include iostream using namespace std; int a[20010]; // 存放原来的数字 int keys[10]; // 密码本 int main() { int n; cin n; // 输入原来的数字 for(int i 0; i n; i) { cin a[i]; } // 输入密码本 for(int i 0; i 10; i) { cin keys[i]; } // 输出加密后的数字 for(int i 0; i n; i) { cout keys[a[i]] ; } cout endl; return 0; }八、为什么这样写1、来看这一句cout keys[a[i]];很多同学第一次看到都会发懵。其实一点也不复杂。2、例如i31那么a[3] 42于是keys[a[3]] ↓ keys[4] ↓ 33所以输出33、可以把它理解成先从原数组里拿到数字再把这个数字当作密码本的页码翻到对应的一页找到新的数字并输出。因此keys[a[i]]4、其实就是两步1第一步a[i]得到42第二步keys[4]得到3整个过程十分自然。九、这道题真正考察什么1、很多同学觉得老师这不是一道数组题吗2、其实它真正考察的是一种非常重要的编程思想——映射Mapping。所谓映射就是建立一种对应关系。3、例如学生编号 → 学生姓名 身份证号 → 身份信息 英文 → 中文 密码 → 原文 数字 → 新数字它们都有一个共同特点知道一个值就能快速找到另一个对应的值。4、在这道题中就是原数字 ↓ keys[] ↓ 新数字以后学习map、unordered_map时就是在做各种各样的映射。十、本题知识总结这道题虽然不难但包含了三级考试中几个非常重要的知识点⭐数组存储数据使用a[]保存原始数字使用keys[]保存密码本。⭐数组下标访问利用keys[a[i]]快速查找对应关系。⭐映射思想用数组建立原数字 → 新数字的对应关系这是后续学习哈希表、字符转换等内容的重要基础。⭐顺序模拟按照题目的要求从左到右依次处理每一个数字不遗漏、不跳步。 举一反三学会了这道题你已经能够解决很多类似的问题例如 字母替换A→ZB→Y…… 成绩等级转换90→A80→B…… 摩斯密码转换 DNA 碱基互补配对A↔TC↔G 字符串加密与解密 哈希映射的基础应用可以说这是一道难度不高但价值很高的基础题真正掌握了它以后遇到各种查表替换类题目都会迎刃而解。
