OJ105 母牛制造的回文题目据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。你的工作就是去这些牛制造的奇观(最棒的回文)。在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母A-Z和a-z。要你寻找的最长的回文的文章是一个不超过20,000个字符的字符串。我们将保证最长的回文不会超过2,000个字符(在除去标点符号、空格之前)。输入范例Confucius say: Madam, Im Adam.输出范例11Madam, Im Adam个人总结首先提取原始输入中的所有字母并记录其原始位置然后在纯字母数组上分别以单字符和双字符为中心向两侧扩展找到最长回文后通过位置映射回原始字符串输出。代码#includebits/stdc.h using namespace std; #define MAX_INPUT 20000 #define MAX_LETTER 2000 char original[MAX_INPUT 10]; // 存储原始输入 int orig_len 0; // 原始字符串长度 int letter_pos[MAX_LETTER]; // 字母在original中的下标 int letter_count 0; // 字母个数 char letters[MAX_LETTER]; // 只保留字 bool isLetter(char c) { return (cacz)||(cAcZ); } void findLongestPalindrome(int start, int end) { int max_len 0; int best_start 0, best_end 0; for (int center 0; center letter_count; center) { int left center, right center; while (left 0 right letter_count letters[left] letters[right]) { int cur_len right - left 1; if (cur_len max_len) { max_len cur_len; best_start left; best_end right; } left--; right; } } for (int center 0; center letter_count - 1; center) { int left center, right center 1; while (left 0 right letter_count letters[left] letters[right]) { int cur_len right - left 1; if (cur_len max_len) { max_len cur_len; best_start left; best_end right; } left--; right; } } start letter_pos[best_start]; end letter_pos[best_end]; } int main() { char ch; while ((ch getchar()) ! EOF orig_len MAX_INPUT) { original[orig_len] ch; } for (int i 0; i orig_len; i) { if (isLetter(original[i])) { letter_pos[letter_count] i; letters[letter_count] toupper(original[i]); letter_count; } } int start, end; findLongestPalindrome(start, end); int letter_len 0; for (int i start; i end; i) { if (isLetter(original[i])) letter_len; } cout letter_len endl; for (int i start; i end; i) { cout original[i]; } cout endl; return 0; }109 大实数加法题目给你两个正的实数A和B你的任务是计算出AB的值。本题目包含T组测试数据。每一组测试数据在一行里面包含两个长度不大于400的正实数A和BA和B均无多余的前导0。对于每一组测试数据请在一行里面输出输出AB的值行首与行尾均无空格。运算结果最后的0比如1.400不需要输出输出为1.4。个人总结将大实数根据小数点分成两部分--整数部分和小数部分整数部分在前面补0使得两个数长度相等小数部分在后面补0是的长度相等。代码#includebits/stdc.h using namespace std; //去掉末尾0 string removeZero(string s) { if(s.find(.)string::npos) return s; while(s.back()0) s.pop_back(); if(s.back().) s.pop_back(); return s; } string Add(string a,string b) { int index1-1;//小数点位置索引 int index2-1; for(int i0;ia.length();i) { if(a[i].) index1i; } for(int j0;jb.length();j) { if(b[j].) index2j; } if(index1-1)//只有整数部分 { a.; index1a.length()-1; } if(index2-1) { b.; index2b.length()-1; } string integer_aa.substr(0,index1);//整数部分 string dec_aa.substr(index11);//小数部分 string integer_bb.substr(0,index2); string dec_bb.substr(index21); while(dec_a.length()dec_b.length()) dec_a0; while(dec_b.length()dec_a.length()) dec_b0; string dec_result; int carry0; for(int idec_a.length()-1;i0;i--) { int sum(dec_a[i]-0)(dec_b[i]-0)carry; dec_resultchar(sum%100)dec_result; carrysum/10; } while(integer_a.length()integer_b.length()) integer_a0integer_a; while(integer_b.length()integer_a.length()) integer_b0integer_b; string integer_result; for(int iinteger_a.length()-1;i0;i--) { int sum(integer_a[i]-0)(integer_b[i]-0)carry; integer_resultchar(sum%100)integer_result; carrysum/10; } if(carry0) integer_resultchar(carry0); string resultinteger_result.dec_result; resultremoveZero(result); return result; } int main() { string A,B; int T; cinT; while(T--) { cinAB; coutAdd(A,B)endl; } return 0; }123 汉诺塔问题第m步--递归题目给定三根杆A、B、C和大小不同的几个盘子。这些盘子按尺寸递减顺序套在A杆上最小的在最上面。现在的任务是把这些盘子从A杆移到C杆且保持原来堆放顺序。在实现任务时每次只能移动一个盘子且任何时刻不允许大的盘子放在小的盘子上面B杆可以作为辅助存放杆。求总共有n个圆盘时搬动过程中的第m步是从哪个杆到哪个杆。输入你的程序需要从标准输入设备通常为键盘中读入多组测试数据。每组输入数据由一行组成每行输入一个整数表示盘子数n1≤n≤10以及步数m两个数据之间以一个空格分隔。行首和行尾没有多余的空格两组数据之间也没有多余的空行。输出对每组测试数据你的程序需要向标准输出设备通常为启动该程序的终端依次输出一行对应的答案该行中输出第m步移动的情况如第m步是从A移到B则输出“A--B”不包括引号。如果移动过程不存在第m步则输出“none” 不包括引号。两组数据之间无空行第一组前及最后一组后也无空行。输入范例2 32 4输出范例B--Cnone个人总结移动过程先把n-1个盘子从A移动到B借助C然后把第n个盘子从A移到C再把n-1个盘子从B移到C借助A。代码#includeiostream using namespace std; int step0; //记录当前步数 int m0; //目标步数 bool foundfalse; //是否找到目标步数 void move(char x, char y) { step; if(step m) { printf(%c--%c\n,x,y); foundtrue; } } bool hanoi(int n, char A, char B, char C) { if (found) return false; // 已找到停止递归 if (n0) return true; if (!hanoi(n-1,A,C,B)) return false; move(A,C); if (found) return false; if(!hanoi(n- 1, B,A,C)) return false; return true; } int main() { int n; while(cinnm) { step0; foundfalse; hanoi(n,A,B,C); if(!found) { printf(none\n); } } return 0; }英语大多数程序仅由少数几种步骤构成这些步骤会在程序中以不同场景和组合反复出现。最常见的步骤是执行一些计算然后按照程序员指定的顺序进入程序的下一步。程序常常需要重复执行一小段步骤例如遍历游戏分数列表并找出最高分。这种重复的代码序列被称为循环loops。计算机之所以如此实用其中一项关键能力就是能根据处理的数据值做出条件判断并执行不同指令。if-then-else 语句就实现了这一功能它会测试某段数据再根据测试结果选择两段指令序列中的一段。这些备选指令中可能包含goto 语句用于引导计算机从程序的其他位置选取下一条指令。例如程序可能会比较两个数字并根据比较结果跳转到程序的不同部分。程序经常会多次使用某一段特定的步骤序列。这类步骤序列可以被组合成子程序subroutine之后在主程序的不同位置按需调用或访问。每次调用子程序时计算机会记住调用发生时程序的执行位置以便在子程序执行完毕后返回该位置。在每次调用前程序可以指定子程序使用不同的数据这让一段通用代码只需编写一次就能以多种方式复用。大多数程序会使用多种类型的子程序其中最常见的包括函数functions、过程procedures、库例程library routines、系统例程system routines和设备驱动程序device drivers。函数是计算某个值的小型子程序例如计算角度 —— 这类计算无法通过单条基础指令完成。过程则执行更复杂的功能比如对一组姓名进行排序。库例程是为多个不同程序编写的通用子程序。系统例程与库例程类似但实际存在于操作系统中它们为应用程序提供服务比如打印一行文本。设备驱动程序是添加到操作系统中的系统例程用于让计算机与新设备如扫描仪、调制解调器或打印机通信。设备驱动程序通常包含可直接作为应用程序执行的功能这允许用户直接控制设备 —— 例如在更换墨盒后需要重新校准彩色打印机以获得最佳打印质量时这一功能就非常实用。现代计算机通常将程序存储在某种可随机访问的磁性存储介质上比如计算机内置的硬盘。这类磁盘上的额外信息称为目录directories会记录磁盘上各程序的名称、写入时间以及程序在磁盘介质上的起始位置。当用户指示计算机执行某个应用程序时操作系统会遍历这些目录定位到程序并将其副本读入随机存取存储器RAM随后引导 ** 中央处理器CPU** 从程序开头开始执行指令。程序开头的指令会为计算机处理信息做好准备在 RAM 中定位空闲内存位置以存储工作数据从磁盘中读取用户设置的标准选项和默认值并在显示器上绘制初始界面。应用程序会通过调用系统例程来获取用户输入的信息副本操作系统会将输入的数据转换为标准内部格式。随后应用程序会利用这些信息决定下一步操作 —— 例如执行文本页面重排版等所需的处理功能或从磁盘上的其他文件中获取额外信息。无论哪种情况都会通过调用其他系统例程来实际执行结果显示或磁盘文件访问操作。当应用程序执行完毕或收到退出指令时会进一步发起系统调用确保所有需要保存的数据都已写回磁盘之后再向操作系统发出最终系统调用表明程序已结束。操作系统随后会释放该应用程序占用的 RAM 及相关设备资源等待用户下达启动其他程序的指令。英语单词背诵是计算机英语文章后面的单词
3月15日打卡
OJ105 母牛制造的回文题目据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。你的工作就是去这些牛制造的奇观(最棒的回文)。在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母A-Z和a-z。要你寻找的最长的回文的文章是一个不超过20,000个字符的字符串。我们将保证最长的回文不会超过2,000个字符(在除去标点符号、空格之前)。输入范例Confucius say: Madam, Im Adam.输出范例11Madam, Im Adam个人总结首先提取原始输入中的所有字母并记录其原始位置然后在纯字母数组上分别以单字符和双字符为中心向两侧扩展找到最长回文后通过位置映射回原始字符串输出。代码#includebits/stdc.h using namespace std; #define MAX_INPUT 20000 #define MAX_LETTER 2000 char original[MAX_INPUT 10]; // 存储原始输入 int orig_len 0; // 原始字符串长度 int letter_pos[MAX_LETTER]; // 字母在original中的下标 int letter_count 0; // 字母个数 char letters[MAX_LETTER]; // 只保留字 bool isLetter(char c) { return (cacz)||(cAcZ); } void findLongestPalindrome(int start, int end) { int max_len 0; int best_start 0, best_end 0; for (int center 0; center letter_count; center) { int left center, right center; while (left 0 right letter_count letters[left] letters[right]) { int cur_len right - left 1; if (cur_len max_len) { max_len cur_len; best_start left; best_end right; } left--; right; } } for (int center 0; center letter_count - 1; center) { int left center, right center 1; while (left 0 right letter_count letters[left] letters[right]) { int cur_len right - left 1; if (cur_len max_len) { max_len cur_len; best_start left; best_end right; } left--; right; } } start letter_pos[best_start]; end letter_pos[best_end]; } int main() { char ch; while ((ch getchar()) ! EOF orig_len MAX_INPUT) { original[orig_len] ch; } for (int i 0; i orig_len; i) { if (isLetter(original[i])) { letter_pos[letter_count] i; letters[letter_count] toupper(original[i]); letter_count; } } int start, end; findLongestPalindrome(start, end); int letter_len 0; for (int i start; i end; i) { if (isLetter(original[i])) letter_len; } cout letter_len endl; for (int i start; i end; i) { cout original[i]; } cout endl; return 0; }109 大实数加法题目给你两个正的实数A和B你的任务是计算出AB的值。本题目包含T组测试数据。每一组测试数据在一行里面包含两个长度不大于400的正实数A和BA和B均无多余的前导0。对于每一组测试数据请在一行里面输出输出AB的值行首与行尾均无空格。运算结果最后的0比如1.400不需要输出输出为1.4。个人总结将大实数根据小数点分成两部分--整数部分和小数部分整数部分在前面补0使得两个数长度相等小数部分在后面补0是的长度相等。代码#includebits/stdc.h using namespace std; //去掉末尾0 string removeZero(string s) { if(s.find(.)string::npos) return s; while(s.back()0) s.pop_back(); if(s.back().) s.pop_back(); return s; } string Add(string a,string b) { int index1-1;//小数点位置索引 int index2-1; for(int i0;ia.length();i) { if(a[i].) index1i; } for(int j0;jb.length();j) { if(b[j].) index2j; } if(index1-1)//只有整数部分 { a.; index1a.length()-1; } if(index2-1) { b.; index2b.length()-1; } string integer_aa.substr(0,index1);//整数部分 string dec_aa.substr(index11);//小数部分 string integer_bb.substr(0,index2); string dec_bb.substr(index21); while(dec_a.length()dec_b.length()) dec_a0; while(dec_b.length()dec_a.length()) dec_b0; string dec_result; int carry0; for(int idec_a.length()-1;i0;i--) { int sum(dec_a[i]-0)(dec_b[i]-0)carry; dec_resultchar(sum%100)dec_result; carrysum/10; } while(integer_a.length()integer_b.length()) integer_a0integer_a; while(integer_b.length()integer_a.length()) integer_b0integer_b; string integer_result; for(int iinteger_a.length()-1;i0;i--) { int sum(integer_a[i]-0)(integer_b[i]-0)carry; integer_resultchar(sum%100)integer_result; carrysum/10; } if(carry0) integer_resultchar(carry0); string resultinteger_result.dec_result; resultremoveZero(result); return result; } int main() { string A,B; int T; cinT; while(T--) { cinAB; coutAdd(A,B)endl; } return 0; }123 汉诺塔问题第m步--递归题目给定三根杆A、B、C和大小不同的几个盘子。这些盘子按尺寸递减顺序套在A杆上最小的在最上面。现在的任务是把这些盘子从A杆移到C杆且保持原来堆放顺序。在实现任务时每次只能移动一个盘子且任何时刻不允许大的盘子放在小的盘子上面B杆可以作为辅助存放杆。求总共有n个圆盘时搬动过程中的第m步是从哪个杆到哪个杆。输入你的程序需要从标准输入设备通常为键盘中读入多组测试数据。每组输入数据由一行组成每行输入一个整数表示盘子数n1≤n≤10以及步数m两个数据之间以一个空格分隔。行首和行尾没有多余的空格两组数据之间也没有多余的空行。输出对每组测试数据你的程序需要向标准输出设备通常为启动该程序的终端依次输出一行对应的答案该行中输出第m步移动的情况如第m步是从A移到B则输出“A--B”不包括引号。如果移动过程不存在第m步则输出“none” 不包括引号。两组数据之间无空行第一组前及最后一组后也无空行。输入范例2 32 4输出范例B--Cnone个人总结移动过程先把n-1个盘子从A移动到B借助C然后把第n个盘子从A移到C再把n-1个盘子从B移到C借助A。代码#includeiostream using namespace std; int step0; //记录当前步数 int m0; //目标步数 bool foundfalse; //是否找到目标步数 void move(char x, char y) { step; if(step m) { printf(%c--%c\n,x,y); foundtrue; } } bool hanoi(int n, char A, char B, char C) { if (found) return false; // 已找到停止递归 if (n0) return true; if (!hanoi(n-1,A,C,B)) return false; move(A,C); if (found) return false; if(!hanoi(n- 1, B,A,C)) return false; return true; } int main() { int n; while(cinnm) { step0; foundfalse; hanoi(n,A,B,C); if(!found) { printf(none\n); } } return 0; }英语大多数程序仅由少数几种步骤构成这些步骤会在程序中以不同场景和组合反复出现。最常见的步骤是执行一些计算然后按照程序员指定的顺序进入程序的下一步。程序常常需要重复执行一小段步骤例如遍历游戏分数列表并找出最高分。这种重复的代码序列被称为循环loops。计算机之所以如此实用其中一项关键能力就是能根据处理的数据值做出条件判断并执行不同指令。if-then-else 语句就实现了这一功能它会测试某段数据再根据测试结果选择两段指令序列中的一段。这些备选指令中可能包含goto 语句用于引导计算机从程序的其他位置选取下一条指令。例如程序可能会比较两个数字并根据比较结果跳转到程序的不同部分。程序经常会多次使用某一段特定的步骤序列。这类步骤序列可以被组合成子程序subroutine之后在主程序的不同位置按需调用或访问。每次调用子程序时计算机会记住调用发生时程序的执行位置以便在子程序执行完毕后返回该位置。在每次调用前程序可以指定子程序使用不同的数据这让一段通用代码只需编写一次就能以多种方式复用。大多数程序会使用多种类型的子程序其中最常见的包括函数functions、过程procedures、库例程library routines、系统例程system routines和设备驱动程序device drivers。函数是计算某个值的小型子程序例如计算角度 —— 这类计算无法通过单条基础指令完成。过程则执行更复杂的功能比如对一组姓名进行排序。库例程是为多个不同程序编写的通用子程序。系统例程与库例程类似但实际存在于操作系统中它们为应用程序提供服务比如打印一行文本。设备驱动程序是添加到操作系统中的系统例程用于让计算机与新设备如扫描仪、调制解调器或打印机通信。设备驱动程序通常包含可直接作为应用程序执行的功能这允许用户直接控制设备 —— 例如在更换墨盒后需要重新校准彩色打印机以获得最佳打印质量时这一功能就非常实用。现代计算机通常将程序存储在某种可随机访问的磁性存储介质上比如计算机内置的硬盘。这类磁盘上的额外信息称为目录directories会记录磁盘上各程序的名称、写入时间以及程序在磁盘介质上的起始位置。当用户指示计算机执行某个应用程序时操作系统会遍历这些目录定位到程序并将其副本读入随机存取存储器RAM随后引导 ** 中央处理器CPU** 从程序开头开始执行指令。程序开头的指令会为计算机处理信息做好准备在 RAM 中定位空闲内存位置以存储工作数据从磁盘中读取用户设置的标准选项和默认值并在显示器上绘制初始界面。应用程序会通过调用系统例程来获取用户输入的信息副本操作系统会将输入的数据转换为标准内部格式。随后应用程序会利用这些信息决定下一步操作 —— 例如执行文本页面重排版等所需的处理功能或从磁盘上的其他文件中获取额外信息。无论哪种情况都会通过调用其他系统例程来实际执行结果显示或磁盘文件访问操作。当应用程序执行完毕或收到退出指令时会进一步发起系统调用确保所有需要保存的数据都已写回磁盘之后再向操作系统发出最终系统调用表明程序已结束。操作系统随后会释放该应用程序占用的 RAM 及相关设备资源等待用户下达启动其他程序的指令。英语单词背诵是计算机英语文章后面的单词
