c语言 打表法,信息学竞赛中的算法技巧-打表法详解
原标题：信息学竞赛中的算法技巧-打表法详解
打表是算法竞赛中的一个技巧，这个技巧对于一些题目而言能够降低程序的运行时间，降低算法的时间复杂度。
《算法笔记》里面也有写到：举个例子，如果需要判断输入一个是哪几个素数相乘而得，例如12 = 2*2*3，我们就需要判断哪些是素数，如果对于输入的数，我们有一个循环，在循环里面判断是不是素数，是，就看能不能整除输入的数，不能，就下一个；
这时候就有个问题，如果每次都在循环里面判断是否是素数，就是有O(M)的时间复杂度，再加上本身就在一个大循环内部，所以这样进行程序设计的时间复杂度就有O(N^2)。
为了降低时间复杂度，我们可以使用打表的技巧，在主程序外部我们先建立一个素数表，用于查询某个数是否是素数，之后再在程序的循环里面直接调用查询，时间复杂度为O(1)。
总结打表的几个优点：
① 在程序中一次性计算出需要的结果，之后直接查询，一般情况下，Q次查询的时间复杂度只需要O(n+Q)；
② 对于一些题目，数据范围非常大，可以暴力计算小范围数据结果，然后找规律。
打表就是将所有输入情况的答案保存在代码中，输入数据后直接输出就可以了
打表法具有 快速，易行(可以写暴力枚举程序)的特点， 缺点是代码可能太大，或者情况覆盖不完
对于不会超时，数据规模适合打表，为了简洁你也可以打表
例一：NOIP2008T2
Problem Deion
给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数(若该数非零，则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示：
注意：
1. 加号与等号各自需要两根火柴棍
2. 如果A≠B，则A+B=C与B+A=C视为不同的等式(A、B、C≥0)
3. n根火柴棍必须全部用上
Input
输入一个整数n(n≤24)。
Output
输出能拼成的不同等式的数目。
这道题n<=20完全可以打表，代码( 生成答案)：
#include
#include
#include
using namespace std;
int main{
freopen("ans.txt","w",stdout);
int a[10]={6,2,5,5,4,5,6,3,7,6};
int i,j,temp=0,num=0,k,in[2020],n;
in[0]=6;
for(i=1;i<=2000;i++){
k=i;
temp=0;
<本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！