一个小小的算法题

﹏ヽ暗。殇╰゛Y 2021-11-10 14:58 260阅读 0赞

> 写在前面  
> 我们对一个算法优化的操作，除了是对思维角度的改变，还有针对具体情况进行分类细化。

> /\*题目：一个整数，它加上100后是一个完全平方数，在加上168又是一个完全平方数，请该数为多少？  
> 现在一共有两个条件：1.加上100是一个数的苹方 2.加上268又是一个数的平方  
> 所以，最大范围就是他俩是相邻俩个数的苹方 得到式子(x+1)^2 -x^2 =168;(x+1)^2 =num+268;x^2 =num+100;  
> 解得x=83.5,所以取x为84，得到num=6956;所以在6956范围内找这个数  
> \*/

这边我是用js来写的。

## 解法一 ##

这个解法很明显，就是遍历6956，然后这个数加上100和268，再平方根，取整，验证这两个整数。这个想法是从题目本身出发，每一个数的循环，然后找到四个数，下面是运行结果，  
![在这里插入图片描述][20190803165417815.png]  
但是仔细分析一个这个解法，循环了七千次，而我们的答案只有三个，绝大多数是无效的循环，

## 解法二 ##

var timestamp7 = (new Date()).valueOf();
    var count = 0;
          for(let i = 84;i>=10;i--){
            for(let j = i-1;j>=1;j--){
    			count++;
             	 if((i*i-j*j)==168)
               		 console.log(j*j-100)
            }
          }
          var timestamp8 = (new Date()).valueOf();
          var consume4 = timestamp8-timestamp7
          console.log("消耗时间："+consume4)
    	  console.log("循环次数："+count)

这个解法的出发角度是从两个平方数本身出发，两个平方数是相差168的，我们约定大数为A，小数为B，只要将两数排列组合一下，只要两数相差168就符合条件，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5qdW5fZmVp_size_16_color_FFFFFF_t_70]  
计算结果如下，多出一个数是因为上面一个解法没有把负数包含进去，可以看到这里用的时间减小了4倍，这里循环的次数也大概是3500次，减少了大概一半，并且里面不需要平方根操作，所以时间减少了很多  
![在这里插入图片描述][20190803181832625.png]

## 解法三 ##

仔细分析上面的算法，在第二个循环中，如果打印出了答案，那么接下来的循环就是没有必要的，就可以直接进入下一个i循环，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5qdW5fZmVp_size_16_color_FFFFFF_t_70 1]

var count1 = 0;
    	  var timestamp3 = (new Date()).valueOf();
          for(let i = 84;i>=10;i--){
            for(let j = i-1;j>=1;j--){
    			count1++;
              if((i*i-j*j)<168)
                continue;
              if((i*i-j*j)==168)
                console.log(j*j-100)
              if((i*i-j*j)>168)
                j=0
            }
          }
          var timestamp4 = (new Date()).valueOf();
          var consume2 = timestamp4-timestamp3
          console.log("消耗时间："+consume2)
    	  console.log("循环次数："+count1)

运行结果如下所示，可以看到循环次数大大的减小了，理论上时间会缩短不到十倍，

![在这里插入图片描述][2019080318321386.png]

## 解法四 ##

解法三是将正解之后的无用循环去掉，那么再想想，正解之前的循环是不是也可以去掉呢？因为A是递减循环的，所以我们设A的值为x1，然后B循环了y1次发现差值等于168，我们记录下这个y1，然后A的值为X2，然后循环了y2次发现差值等于168，记录y2。所以得到以下结果：

x1>x2
    x1>y1>0
    x2>y2>0
    x1^2-(x1-y1)^2=x2^2-(x2-y2)^2
    证：y1<y2

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5qdW5fZmVp_size_16_color_FFFFFF_t_70 2]  
所以说在每次循环之前也是有好多次是肯定是找不到正解的，所以也需要在循环之前就快速定位到正解的大概区间

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5qdW5fZmVp_size_16_color_FFFFFF_t_70 3]  
代码如下：

可以看到结果是只循环了155次，减少了一小半的时间，也就是说，每次j循环两轮就可以判断是否有解，

![在这里插入图片描述][20190803183402864.png]

## 总结 ##

在分析一个算法的时候，进入算法内部，分析哪些操作是每次都去做而没用的，就需要去掉，而最后一种解法可以称之为动态规划，记忆每次循环的次数，为下次循环的最小次数。

## 最后 ##

在这85个中其实也只有四个是有正解的，能不能把这85个也精简呢？

[20190803165417815.png]: /images/20211109/f5b6dbde816b4c78942a60cbddc48e0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5qdW5fZmVp_size_16_color_FFFFFF_t_70]: /images/20211109/b43b0d3e8e4149d584e4c7ff3fd5aa04.png
[20190803181832625.png]: /images/20211109/b4b8eac869884c8c98e68260dfff496f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5qdW5fZmVp_size_16_color_FFFFFF_t_70 1]: /images/20211109/db8bef652fc047ca980577e8e8737ba2.png
[2019080318321386.png]: /images/20211109/8634ba3779fe4d01af47e2b2e6657920.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5qdW5fZmVp_size_16_color_FFFFFF_t_70 2]: /images/20211109/90d9c3bc2dc44d17b5fb296248cc52ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5qdW5fZmVp_size_16_color_FFFFFF_t_70 3]: /images/20211109/a8cbe93c110f4d29a257cd48522d4321.png
[20190803183402864.png]: /images/20211109/3aefa64a0d2142eeb150b3023b7307fa.png