C++NOIP算法课程第一章.ppt

【C++ NOIP算法课程第一章】主要探讨的是如何在C++中进行高精度计算，这是在编程竞赛，尤其是信息学奥林匹克竞赛（NOIP）中常见的问题。高精度计算旨在处理超过标准数据类型所能表示的数值范围，以满足极高精度的需求。 1. **数据接收与存储**：对于大数的输入，C++可以使用字符串方式。例如，通过`cin>>s`读取一个字符串`s`，然后将字符串转换为数组，存储每一位数字。这通常涉及到字符串函数的使用，如`length()`获取字符串长度，以及对字符串字符的遍历和转换。另一种方法是直接通过循环和数组输入数据，但这通常需要更多的编程技巧来实现。 2. **确定数位数**：在高精度计算中，数的位数是关键。对于由字符串输入的数，位数就是字符串的长度。数组的第一位通常是用于存储位数，例如`a[0]=s.length()`。 3. **进位与借位处理**： - **加法进位**：在加法操作中，如果当前位相加后的结果大于等于10，则需要进位。例如，`c[i]=a[i]+b[i];`，如果`c[i]>=10`，则`c[i]%=10; ++c[i+1];`。 - **减法借位**：在减法操作中，如果被减数小于减数，则需要向前一位借位。例如，`if (a[i]<b[i]) { --a[i+1]; a[i]+=10; }`，之后计算差值`c[i]=a[i]-b[i];`。 - **乘法进位**：在乘法中，需要考虑每一位的乘积与其他位的和，可能需要进位。例如，`c[i+j-1]= a[i]*b[j] + x + c[i+j-1];`，并将结果对10取模，更新进位值`x = c[i+j-1]/10;`。 4. **商和余数的求法**：在除法操作中，处理商和余数的方法会更复杂，通常需要根据被除数和除数的具体情况来设计算法。 5. **高精度加法**：高精度加法可以通过模拟小学竖式加法的方式实现。例如，创建三个数组`A`、`B`和`C`，分别存储被加数、加数和结果。遍历数组，逐位相加，并处理进位。如示例代码所示，使用`while`循环遍历数组，直到没有更多的元素需要处理。在这个过程中，`x`用于存储进位，`c[i]%=10`确保每一位不超过10。 在实际编程中，为了处理输入的字符串，通常还需要额外的代码来将字符串转换为整数数组。例如，`main`函数中的`strlen()`用于获取字符串长度，`sscanf()`或`atof()`等函数用于将字符串转换为数值。结果通常也需要格式化输出，这可能涉及`printf`或其他输出函数。 这个课程适合想要参加蓝桥杯、信息学奥赛等编程竞赛的学生，或者是对C++编程和算法感兴趣的自学者。它提供了一套完整的教学框架，帮助孩子们理解和掌握高精度计算的方法，为参与编程竞赛做好准备。