无忧启动论坛

标题: psh（Perl shell） 下计算 “等腰勾股数”的一行代码 [打印本页]
作者: 不点    时间: 2015-11-19 13:26
标题: psh（Perl shell） 下计算 “等腰勾股数”的一行代码
本帖最后由 不点 于 2015-11-19 13:29 编辑

大家都知道勾股数是什么（百度可查）。比如，3、4、5 就是一组勾股数。勾股数有无穷多组。

今天讨论的是一类特殊的勾股数：“准等腰”勾股数，简称 “等腰”勾股数。这是我给它们命名的，我也不知道以前有没有人曾经给它命名。

什么意思呢？就是说，这类勾股数很接近等腰直角三角形的三条边。两条直角边肯定不会相等，但它们很接近，只相差 1。

在 Linux 下安装 psh，其项目空间在这里：

https://gnp.github.io/psh/
https://github.com/gnp/psh
http://sourceforge.net/projects/psh/

这里不谈具体的安装步骤，假定你已经安装好了。psh 的提示符是 psh%。下面就是我在命令行敲入的计算程序及其运行结果（是复制、粘贴过来的）。

  1. psh%  for ($c=1; $c<20000000; $c++) { $a=int($c / sqrt(2)); $b= $a + 1; if ($a * $a + $b * $b == $c * $c) { print "$a , $b , $c \n";}}
  2. 0 , 1 , 1
  3. 3 , 4 , 5
  4. 20 , 21 , 29
  5. 119 , 120 , 169
  6. 696 , 697 , 985
  7. 4059 , 4060 , 5741
  8. 23660 , 23661 , 33461
  9. 137903 , 137904 , 195025
  10. 803760 , 803761 , 1136689
  11. 4684659 , 4684660 , 6625109
  12. psh%
复制代码


psh 比 bash 强的地方在于，它具有 perl 的语法，能够进行浮点数运算。bash 没有内置的浮点数计算功能，只能通过 bc 等外部命令来间接实现，这是不方便的。我猜，将来的新版 bash 有可能支持浮点数计算，否则肯定是个缺憾。以上程序代码很难在 bash 下实现；就算能够通过 bc 等方式间接实现，那会提高复杂度，因而其代码的可读性也就不会太好了。

作者: wylgogogo    时间: 2015-11-19 21:38
    哎，不懂。完全看不懂。汗。
作者: liaoyin    时间: 2015-11-19 22:37
大神现在在玩linux操作系统了吗？
作者: 不点    时间: 2015-11-20 06:50
本帖最后由 不点 于 2015-11-20 07:06 编辑
liaoyin 发表于 2015-11-19 22:37
大神现在在玩linux操作系统了吗？


linux 没有什么卵用，只是偶尔在特殊的情况下有点用罢了。

linux 的长处，在于命令行功能很好很强大，其他方面则没什么可圈可点之处（个人一管之见）。

linux 有很多 shell，具有不同的功能。但基本的功能是一样的，类似于 Windows 下的 cmd 命令窗口。

有时也把 cmd 的环境称为 dos 环境。它就是微软的命令解释器。

不过，windows 下也只有这么一个命令解释器，相比于 linux 下的众多命令解释器来说，实在是太少了。

windows 的 cmd 命令解释器，功能非常简单，微软没打算让它成就一个大气候，只打算让它当配角。

所以，微软不会花费很大力气去打造这个 cmd。微软逐步淘汰 dos，不想让命令行能做事。

微软想让任何事情，不管是大事还是芝麻小事，都通过庞大的图形界面的 windows 来做。



作者: liaoyin    时间: 2015-11-25 21:43
我在我的个人PC上装过UNUBTU LINUX、红旗６.０、红帽和Centos.感觉装一些合适的应用程序确实是太难了。
作者: 2012tzyx    时间: 2015-11-26 23:52
这么多美元符号也是醉了
作者: 不点    时间: 2015-12-8 21:59
今天了解到 ksh 支持浮点数的计算。因此，有理由相信，bash 今后也会支持浮点数。
作者: 不点    时间: 2017-8-6 11:51
psh 多年未更新，不能在 ARM linux 下顺利编译。从上次发帖到现在，又过了两年，bash 也仍旧不支持浮点计算。所幸 zsh 支持浮点，同时 zsh 支持所有的 CPU 架构，而且在持续不断地更新，因此尝试用 zsh 实现。

# version 3,  latest version

  1. #!/bin/zsh
  2. integer a b c;
  3. for (( a = 0; a < 5000000; a++ ))
  4. do
  5.         b=$((a + 1))
  6.         c=$((b*(2**0.5)))
  7.         if (( b * b == (c + a) * (c - a) ))
  8.         then
  9.                 echo "$a, $b, $c";
  10.         fi
  11. done
复制代码


顺便说明一下，如果需要在 zsh 下使用数学函数（sqrt，sin，cos，atan 等），需要在 zsh 下首先执行一条 zmodload  zsh/mathfunc 命令才行。

# old version 2

  1. #!/bin/zsh
  2. integer a c;
  3. float a1 a2 old_diff;
  4. old_diff=$((0.8))
  5. for (( a = 0; a < 5000000; a++ ))
  6. do
  7. a1=$(((a + 0.5)*(2**0.5)))
  8. a2=$(((a + 1.0)*(2**0.5)))
  9. c=$((a2))
  10. if ((c > a1 && c - a1 < old_diff ))
  11. then
  12. echo "$a, $((a + 1)), $c, $((a1)), $((a2))";
  13. old_diff=$((c-a1))
  14. fi
  15. done
复制代码


# old version 1

  1. #!/bin/zsh
  2. integer a b c;
  3. for (( c = 1; c < 20000000; c++))
  4. do
  5. a=$((c/2**0.5));
  6. b=$((a + 1));
  7. if (( $a * $a + $b * $b == $c * $c ))
  8. then
  9. echo "$a, $b, $c";
  10. fi
  11. done
复制代码

作者: 不点    时间: 2017-8-6 16:55
前面我们对边长从 0 开始逐个进行测试，速度很慢。从前面的输出的结果中发现，斜边边长 c(n) 满足如下规律：

  1. c(n+2) = 6 * c(n+1) - c(n)
复制代码


再根据初值 c(1)=1，c(2)=5，即可求得通项公式（求解过程略）。通项公式有两种等价的表示形式：

  1. c(n) = ( (2 - sqrt(2)) / 4 * (3 + sqrt(8))**n ) + ( (2 + sqrt(2)) / 4 * (3 - sqrt(8))**n )
复制代码

  1. c(n) = ( (sqrt(2)) / 4 * (sqrt(2) + 1)**(n+n-1) ) + ( (sqrt(2)) / 4 * (sqrt(2) - 1)**(n+n-1) )
复制代码


其中，双星号（**）表示乘方；“根号 8”其实就是 “2 倍的根号 2”；“n + n - 1”其实就是“ 2n - 1”。

有了通项公式，求解算法就优化了。下面的程序采用上述第一个通项公式。注意，通项公式中有两项（是相加的关系），被加数（第二项）总是小于 1，因此，暂时忽略不计。我们紧接着执行了一条 ((c++))，（注意 c 本身是整数，会自动进行取整），这样就弥补了刚才未加第二项所带来的损失。和前面的程序一样，我们用 2**0.5（即 2 的 0.5 次方） 来表示“根号2”，为的是尽量避免使用数学库函数 sqrt 。

  1. #!/bin/zsh
  2. integer a b c n;
  3. for (( n = 1; n < 15; n++))
  4. do
  5.         c=$(((2 - (2**0.5))/4*((3+(8**0.5))**n)));
  6.         ((c++));
  7.         a=$((c/2**0.5));
  8.         b=$((a + 1));
  9.         if (( $a * $a + $b * $b == $c * $c ))
  10.         then
  11.                 echo "$a, $b, $c";
  12.         fi
  13. done
复制代码


运算结果如下：

  1. 0, 1, 1
  2. 3, 4, 5
  3. 20, 21, 29
  4. 119, 120, 169
  5. 696, 697, 985
  6. 4059, 4060, 5741
  7. 23660, 23661, 33461
  8. 137903, 137904, 195025
  9. 803760, 803761, 1136689
  10. 4684659, 4684660, 6625109
  11. 27304196, 27304197, 38613965
  12. 159140519, 159140520, 225058681
  13. 927538920, 927538921, 1311738121
  14. 5406093003, 5406093004, 7645370045
复制代码
作者: 不点    时间: 2017-8-6 19:28
zsh 支持 C 语言格式的语法，这次可以不用 $ 符号了。只是格式有变动，算法没有任何改动。

  1. #!/bin/zsh
  2. integer a b c n;
  3. for (( n = 1; n < 15; n++))
  4. {
  5.         (( c = (2 - (2**0.5))/4*((3+(8**0.5))**n),
  6.         c++, a = c/2**0.5, b = a + 1));
  7.         if (( a * a + b * b == c * c ))   
  8.         {
  9.                 printf "%d, %d, %d\n" a b c;
  10.         }
  11. }
复制代码





欢迎光临 无忧启动论坛 (http://bbs.c3.wuyou.net/) Powered by Discuz! X3.3