Connect with us

检查素数的正则表达式分享

一般来说,我们会使用正规表达式来做字符串匹配,今天在网上浏览的时候,看到了有人用正则表达式来检查一个数字是否为素数(质数),让我非常感兴趣

Published

on

这个正则表达式如入所示:

检查素数与否的正则表达式

要使用这个正规则表达式,你需要把自然数转成多个1的字符串,如:2 要写成 “11”, 3 要写成 “111”, 17 要写成“11111111111111111”,这种工作使用一些脚本语言可以轻松的完成。

一开始我对这个表达式持怀疑态度,但仔细研究了一下这个表达式,发现是非常合理的,下面,让我带你来细细剖析一下是这个表达式的工作原理。

首先,我们看到这个表达式中有“|”,也就是说这个表达式可以分成两个部分:/^1?$/ 和 /^(11+?)\1+$/

  • 第一部分:/^1?$/, 这个部分相信不用我多说了,其表示匹配“空串”以及字串中只有一个“1”的字符串。
  • 第二部分:/^(11+?)\1+$/,这个部分是整个表达式的关键部分。其可以分成两个部分,(11+?)\1+$,前半部很简单了,匹配以“11”开头的并重复0或n个1的字符串,后面的部分意思是把前半部分作为一个字串去匹配还剩下的字符串1次或多次(这句话的意思是——剩余的字串的1的个数要是前面字串1个数的整数倍)。

可见这个正规则表达式是取非素数,要得到素数还得要对整个表达式求反。通过上面的分析,我们知道,第二部分是最重要的,对于第二部分,举几个例子,

示例一:判断自然数8。我们可以知道,8转成我们的格式就是“11111111”,对于(11+?),其匹配了“11”,于是还剩下“111111”,而\1+$正好匹配了剩下的“111111”,因为,“11”这个模式在“111111”出现了三次,符合模式匹配,返回true。所以,匹配成功,于是这个数不是质数。

示例二:判断自然数11。转成我们需要的格式是“11111111111”(十一个1),对于(11+?),其匹配了“11”(前两个1),还剩下“111111111”(九个1),而\1+$无法为“11”匹配那“九个1”,因为“11”这个模式并没有在“九个1”这个串中正好出现N次。于是,我们的正则表达式引擎会尝试下一种方法,先匹配“111”(前三个1),然后把“111”作为模式去匹配剩下的“11111111”(八个1),很明显,那“八个1”并没有匹配“三个1”多次。所以,引擎会继续向下尝试……直至尝试所有可能都无法匹配成功。所以11是素数。

通过示例二,我们可以得到这样的等价数算算法,正则表达式会匹配这若干个1中有没有出现“二个1”的整数倍,“三个1”的整数倍,“四个1”的整数倍……,而,这正好是我们需要的算素数的算法。现在大家明白了吧。

下面,我们用perl来使用这个正规则表达式不停地输出素数:(关于perl的语法我就不多说了,请注意表达式前的取反操作符)

perl -e’$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print”$_ “while ++$_’

另外,让我们来举一反三,根据上述的这种方法,我们甚至可以用正则表达式来求证某方式是否有解,如:

  • 二元方程:17x + 12y = 51   判断其是否有解的正则表达式是:^(.*)\1{16}(.*)\2{11}$
  • 三元方程:11x + 2y + 5z = 115 判断其是否有解的正则表达式是:^(.*)\1{10}(.*)\2{1}(.*)\3{4}$

大家不妨自己做做练习,为什么上述的两个正则表达式可以判断方程是否有解。如果无法参透其中的奥妙的话,你可以读读这篇英文文章

Continue Reading
Click to comment

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注

Designer

PyCharm+Qt Designer+PyUIC安装配置教程详解

这篇文章主要介绍了PyCharm+Qt Designer+PyUIC安装配置教程详解,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

Published

on

Qt Designer用于像VC++的MFC一样拖放、设计控件

PyUIC用于将Qt Designer生成的.ui文件转换成.py文件

Qt Designer和PyUIC都包含在PyQt5中,所以我们只需要安装PyQt5塻块然后再指定Qt Designer和PyUIC即可

为了避免篇幅过长,本文只讲安装配置,使用可查看“PyCharm+QTDesigner+PyUIC使用教程

一、安装PyQt5

Qt Designer包含在PyQt5中,而PyQt5就是一个python模块,所以我们可以直接通过“pip3 install PyQt5”安装

但是我们这里使用PyCharm集成开发环境,所以直接通过PyCharm安装

打开PyCharm,新建一个项目

二、指定Qt Designer和PyUIC

Name–输入最后工具在菜单中的想呈现名称,比如我这里命名为QTDesigner

Program–designer.exe程序的位置,位于当前所用解析器的Lib\site-packages\pyqt5-tools\designer.exe

Working directory–designer.exe工作路径,设置为$ProjectFileDir$

类似地添加PyUIC,

name—-PyUIC

Program—-PyUIC位于当前解析器的Scripts\pyuic5.exe

Arguments—-$FileName$ -o $FileNameWithoutExtension$.py

Working dirctory—-$ProjectFileDir$

回到主界面“Tools”–“External Tools”即可看到我们添加的QTDesigner和PyUIC

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本小子。

Continue Reading

Designer

PyCharm+Qt Designer+PyUIC安装配置教程详解

这篇文章主要介绍了PyCharm+Qt Designer+PyUIC安装配置教程详解,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

Published

on

Qt Designer用于像VC++的MFC一样拖放、设计控件

PyUIC用于将Qt Designer生成的.ui文件转换成.py文件

Qt Designer和PyUIC都包含在PyQt5中,所以我们只需要安装PyQt5塻块然后再指定Qt Designer和PyUIC即可

为了避免篇幅过长,本文只讲安装配置,使用可查看“PyCharm+QTDesigner+PyUIC使用教程

一、安装PyQt5

Qt Designer包含在PyQt5中,而PyQt5就是一个python模块,所以我们可以直接通过“pip3 install PyQt5”安装

但是我们这里使用PyCharm集成开发环境,所以直接通过PyCharm安装

打开PyCharm,新建一个项目

二、指定Qt Designer和PyUIC

Name–输入最后工具在菜单中的想呈现名称,比如我这里命名为QTDesigner

Program–designer.exe程序的位置,位于当前所用解析器的Lib\site-packages\pyqt5-tools\designer.exe

Working directory–designer.exe工作路径,设置为$ProjectFileDir$

类似地添加PyUIC,

name—-PyUIC

Program—-PyUIC位于当前解析器的Scripts\pyuic5.exe

Arguments—-$FileName$ -o $FileNameWithoutExtension$.py

Working dirctory—-$ProjectFileDir$

回到主界面“Tools”–“External Tools”即可看到我们添加的QTDesigner和PyUIC

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本小子。

Continue Reading

300MPHP

PHP面向对象程序设计

这篇文章主要介绍了PHP面向对象程序设计__tostring()和__invoke()用法,结合实例形式分析了__tostring()和__invoke()功能、用法及相关操作注意事项,需要的朋友可以参考下

Published

on

本文实例讲述了PHP面向对象程序设计__tostring()和__invoke()用法。分享给大家供大家参考,具体如下:

__tostring()魔术方法

将一个对象当做一个字符串来使用时,会自动调用该方法,并且在该方法中,可以返回一定的字符串,以表明该对象转换为字符串之后的结果。该魔术方法比较常用。

注意:如果没有定义该方法,则对象无法当做字符串来使用!

类里面未定义__tostring()方法的例子:

<?php
ini_set('display_errors', 1);
class A{
  public $name;
  public $age;
  public $sex;
  function __construct($name, $age, $sex){
    $this->name = $name;
    $this->age = $age;
    $this->sex = $sex;
  }
}
$obj1 = new A('张三', 15, '男');
echo $obj1;  //echo 后面为字符串,而对象不是字符串,会报错
$v1 = "abc" . $obj1; //.为字符串连接符,会报错
$v2 = "abx" + $obj1; //+为加法运算符,会报错
?>

3个报错内容分别为

Catchable fatal error: Object of class A could not be converted to string
Catchable fatal error: Object of class A could not be converted to string
Notice: Object of class A could not be converted to int

类里面定义__tostring()方法

<?php
ini_set('display_errors', 1);
class A{
  public $name;
  public $age;
  public $sex;
  function __construct($name, $age, $sex){
    $this->name = $name;
    $this->age = $age;
    $this->sex = $sex;
  }
  function __tostring(){
    $str = "姓名:" . $this->name;
    $str .= "年龄:" . $this->age;
    $str .= ",性别:" . $this->sex;
    return $str;  //这里可以返回“任何字符串内容”
  }
}
$obj1 = new A('张三', 15, '男');
echo $obj1;  //调用__tostring(),不会报错
?>

运行结果

姓名:张三年龄:15,性别:男

__invoke()魔术方法

将对象当作函数来使用时,会自动调用该方法。通常不推荐这么做。

class A{
  function __invoke(){
    echo "<br />我是一个对象呀,你别把我当作一个函数来调用啊!";
  }
}
$obj = new A();
$obj();  //此时就会调用类中的方法:__invoke()

Continue Reading

趋势

Copyright © 2017 Zox News Theme. Theme by MVP Themes, powered by WordPress.