打表解题法

打表（用空间换时间）—— 指将需要用到的结果先计算出来，后面需要用到时可以直接查表获得。

1）先将所有的结果全部打出来，之后再挑选需要的。典型例题就是素数打表；（大量查询）

例如在一个需要查询大量Fibonacci数F(n)的问题中，显然每次从头开始计算是非常耗时的；而如果进行预处理，即把所有Fibonacci数预先计算并存在数组中，那么每次查询就只需O(1)的时间复杂度;

2）在程序B中分一次或多次计算出所有需要用到的结果，手工把结果写在程序A的数组中，然后在程序A中就可以直接使用这些结果。（程序中一部分过程消耗的时间过多）

在一个程序中使用暴力算法计算出结果，这样就能直接在源程序中使用这些结果。例如对n皇后问题来说，如果使用的算法不够好，就容易超时，而可以在本地用程序计算出对所有n来说n皇后问题的方案数，然后把算出的结果直接写在数组中，就可以根据题目输入的n来直接输出结果。

3）有些不会做或是找不到规律的，先用暴力程序计算小范围数据结果，然后找规律；

这种用法在数据范围非常大时候容易用到，因为这样的题目可能不是用直接能想到的算法来解决的，而需要寻找一些规律才能得到结果。

例1

#include <iostream>
using namespace std;
int main()
{
    int yy;
    cin>>yy;
    if (yy==1) 
    {
        cout<<"1"<<endl;
    }
    if(yy==2) 
    {
        cout<<"8 1 6"<<endl;   //这些输出的内容 事先计算出来
        cout<<"3 5 7"<<endl;
        cout<<"4 9 2"<<endl;
    }
    if(yy==3) 
    {
        cout<<"17 24 1 8 15 "<<endl;
        cout<<"23 5 7 14 16 "<<endl;
        cout<<"4 6 13 20 22 "<<endl;
        cout<<"10 12 19 21 3 "<<endl;
        cout<<"11 18 25 2 9 "<<endl;
    }
    if(yy==4) 
    {
        cout<<"30 39 48 1 10 19 28 "<<endl;
        cout<<"38 47 7 9 18 27 29 "<<endl;
        cout<<"46 6 8 17 26 35 37 "<<endl;
        cout<<"5 14 16 25 34 36 45 "<<endl;
        cout<<"13 15 24 33 42 44 4 "<<endl;
        cout<<"21 23 32 41 43 3 12 "<<endl;
        cout<<"22 31 40 49 2 11 20 "<<endl; 
    }
}

例2 数1的个数

题目描述

给定一个十进制正整数n（1<=n<=10000），写下从1到n的所有整数，然后数一下其中出现的数字“1”的个数。

例如当n=2时，写下1，2.这样只出现了1个“1”；当n=12时，写下1，2，3，4，5，6，7，8，9，10，11，12。这样出现了5个“1”。

输入

有多组输入，每组输入占一行，每一行有一个数字n;

输出

对于每组输入，输出一行，每行一个正整数，即“1”的个数。

样例输入

2

12

样例输出

1

5

分析

将每一个小于等于n的数字遍历过去，每一个数字进行拆分得到其中的“1”的个数，累加起来即是答案（本题可用DP，为了说明打表，这里就用暴力法）

public static void main(String[] args){
		
    Scanner sc = new Scanner(System.in);
    
    while ( !sc.hasNext("eof") ){ 
        
        int n = sc.nextInt();  
        int count = 0;
        
        for (int i = 1; i <= n; i++){  //遍历小于等于n的所有数
        
            int temp = i;         //复制一份 i 
            
            while (temp > 0){   //拆分
            
                if (temp % 10 == 1){
                    count++;
                }
                
                temp /= 10;
            }
        }
        System.out.println(count);
    }	
}

但是呢，我们发现几个问题：

• 1.无论是100还是200，这两组数据都需要计算100以内的数字的“1”的个数，而且过程完全相同。
• 2.如果我们先输入1000，然后再输入200。实际上，200这个数据早就被计算过了，而这个代码却会去重复计算，浪费时间+内存+电量。
• 3.题目要求的数据范围不大，只有1-10000个数字，每一个数字有对应的一个唯一确定的输出。

  这个时候就可以用打表法。（用个数组，把所有的结果都存进去，用空间换时间）

  public static void main(String[] args){
  		
      int val[] = new int[10010];  //存所有可能的结果
      
      Scanner sc = new Scanner(System.in);
      
      int count = 0;
  
      for(int i = 1; i <= 10000; i++){
          
          int temp = i;
          while (temp > 0){   //拆分
              if (temp % 10 == 1){
                  count++;
              }
              temp /= 10;
          }
          
          val[i] = count;
      }
      
      //因为用了打表，这个程序的输入输出只有3行
      while ( !sc.hasNext("eof") ){    
          
          int n = sc.nextInt();  
          System.out.println(val[n]);
      }	
  }

赏

失败是成功之母

支付宝

微信