Perl编程挑战：子程序与算法实现

内容分享18小时前发布
0 0 0

17、编写一个名为 has – no – e 的子程序，如果给定的单词中没有字母“e”，则返回 True。修改此程序，只打印没有字母“e”的单词，并计算列表中没有字母“e”的单词的百分比。假设单词列表存储在 ‘words.txt’ 文件中，每行一个单词。

以下是对应代码： 


sub has-no-e (Str $word) {
    not defined index $word, "e";
}

my $total-count = 0;
my $count-no-e = 0;

for 'words.txt'.IO.lines -> $line {
    $total-count++;
    if has-no-e $line {
        $count-no-e++;
        say $line;
    }
}

say "=" x 24;
say "Total word count: $total-count";
say "Words without 'e': $count-no-e";
printf "Percentage of words without 'e': %.2f %%", 100 * $count-no-e / $total-count;

18、编写一个名为 uses – only 的子程序，它接受一个单词和一个字母字符串，如果该单词仅包含字母列表中的字母，则返回 True。此外，能否用字母 acefhlo 组成除 “Hoe alfalfa?” 之外的句子？

子程序代码如下： 


sub uses-only (Str $word, Str $available) {
    for 0..$word.chars - 1 -> $idx {
        my $letter = substr $word, $idx, 1;
        return False unless defined index $available, $letter;
    }
    True;
}

可以用字母 acefhlo 组成其他句子，例如 “Call a chef.”。

19、编写一个程序，找出有三个连续双字母的单词。例如，“committee”（c – o – m – m – i – t – t – e – e），要是没有中间的“i”就符合要求；“Mississippi”（M – i – s – s – i – s – s – i – p – p – i），要是去掉那些“i”也符合要求。

程序找出的有三个连续双字母的单词是“bookkeeper”、“bookkeepers”、“bookkeeping”和“bookkeepings”。

可以使用以下两种程序来找出这些单词：

使用循环技术的程序：


sub is_triple_double (Str $word) {
    # Tests if a word contains three consecutive double letters.
    my $i = 0;
    my $count = 0;
    while $i < $word.chars - 1 {
        if substr($word, $i, 1) eq substr($word, $i + 1, 1) {
            $count++;
            return True if $count == 3;
            $i += 2;
        } else {
            $count = 0;
            $i++;
        }
    }
    return False;
}

for 'words.txt'.IO.lines -> $word {
    say $word if is_triple_double $word;
}

使用正则表达式的程序：


for 'words.txt'.IO.lines -> $word {
    say $word if $word ~~ /(.) $0 (.) $1 (.) $2/;
}

也可以在操作系统命令行提示符下使用单行命令： 


$ perl6 -ne '.say if /(.) $0 (.) $1 (.) $2/' words.txt

20、这是另一个《汽车脱口秀》谜题：前几天我在高速公路上开车，碰巧注意到了我的里程表。和大多数里程表一样，它显示六位数字，且只显示整数英里数。例如，如果我的车行驶了300000英里，我会看到3 – 0 – 0 – 0 – 0 – 0。那天我看到的情况非常有趣。我注意到最后四位数字是回文数，即它们正读和反读都一样。例如，5 – 4 – 4 – 5是回文数，所以我的里程表可能显示3 – 1 – 5 – 4 – 4 – 5。一英里后，最后五位数字是回文数。例如，它可能显示3 – 6 – 5 – 4 – 5 – 6。再一英里后，六位数字中的中间四位是回文数。还有更绝的，再一英里后，所有六位数字都是回文数！问题是，我第一次看里程表时上面显示的数字是多少？编写一个程序来测试所有六位数字，并打印出任何满足这些要求的数字。

以下是解决该回文里程表谜题的可能程序： 


sub is-palindrome ($number, $start, $len) {
    # Checks if the relevant substring is a palindrome
    my $substring = substr $number, $start, $len;
    return $substring eq flip $substring;
}

sub check ($num) {
    # Checks whether the integer num has the properties described
    return (
        is-palindrome($num, 2, 4) and
        is-palindrome($num + 1, 1, 5) and
        is-palindrome($num + 2, 1, 4) and
        is-palindrome($num + 3, 0, 6)
    );
}

say 'The following are the possible odometer readings:';
for 1e5 .. 1e6 - 4 -> $number {
    say $number if check $number;
}

另一种方法是使用正则表达式来判断是否为回文数： 


sub check ($num) {
    # Checks whether the integer num has the properties described
    $num ~~ /^..(.)(.)$1$0/ and
    $num + 1 ~~ /^.(.)(.).$1$0/ and
    $num + 2 ~~ /^.(.)(.)$1$0/ and
    $num + 3 ~~ /^(.)(.)(.)$2$1$0/;
}

say 'The following are the possible odometer readings:';
for 1e5 .. 1e6 - 4 -> $number {
    say $number if check $number;
}

第二段代码更短，但执行速度较慢，在我的电脑上执行时间几乎是第一段的两倍。如果需要多次或频繁运行程序，第一种更快的方法可能更好；如果只是一次性计算，可能会更喜欢第二种版本。具体选择由你决定。

21、编写一个名为 nested_sum 的子程序，该子程序接受一个由整数数组组成的数组，并将所有嵌套数组中的元素相加。

以下是几种实现方式：

使用嵌套循环：

perl
my @AoA = [[1, 2], [3], [4, 5, 6]];
sub nested_sum (@array) {
my $sum;
for @array -> $item {
for $item.flat -> $nested_item {
$sum += $nested_item;
}
}
return $sum;
}
say nested_sum @AoA; # -> 21

使用“|”操作符：

perl
my @AoA = [[1, 2], [3], [4, 5, 6]];
sub nested_sum (@array) {
my $sum;
for @array -> $item {
for |$item -> $nested_item {
$sum += $nested_item;
}
}
return $sum;
}
say nested_sum @AoA; # -> 21

使用 map 和归约操作符：

perl
my @AoA = [[1, 2], [3], [4, 5, 6]];
sub nested_sum (@array) {
return [+] map {|$_}, @array;
}
say nested_sum @AoA; # -> 21

递归实现（处理未知嵌套深度）：

perl
my @AoA = [[1,2], [3], [4,5,6], [3, [7,6, [3,2]]]];
sub nested_sum ($input) {
my $sum = 0;
for |$input -> $item {
if $item.WHAT ~~ Int {
$sum += $item;
} else {
$sum += nested_sum $item;
}
}
return $sum;
}
say nested_sum @AoA; # -> 42

22、编写一个名为

cumul-sum

的子程序，它接受一个数字列表并返回累积和；也就是说，返回一个新列表，其中第

i

个元素是原始列表中前

i

个元素的和。


sub cumul-sum (@array) {
    my @cumulative;
    my $partial_sum = 0;
    for @array -> $element {
        $partial_sum += $element;
        push @cumulative, $partial_sum;
    }
    return @cumulative;
}

23、编写一个名为 middle 的子程序，它接受一个列表并返回一个新列表，该新列表包含除第一个和最后一个元素之外的所有元素。

sub middle (@array) { return @array[1..*-2] }

24、编写一个名为chop-it的子程序，该子程序接受一个数组，通过移除数组的第一个和最后一个元素来修改它，并且不返回有意义的值。

以下是两种实现方式：

方式一：使用

shift

和

pop

函数。 


sub chop-it (@array) {
    shift @array;
    pop @array;
    return;
}

方式二：使用切片。 


sub chop-it (@array) {
    @array = @array[1..*-2];
    return;
}

25、编写一个名为is_sorted的子程序，它接受一个数字列表（或数组）作为参数，如果列表按升序排序则返回True，否则返回False。

以下是几种实现方式：

迭代比较方式：


sub is_sorted (@array) {
    my $previous = @array[0];
    for @array -> $current {
        return False if $current < $previous;
        $previous = $current;
    }
    return True;
}

与排序后列表比较方式：


sub is_sorted (@array) {
    return @array eqv @array.sort;
}

使用功能编程和归约超运算符方式：


sub is_sorted (@array) {
    return [<=] @array;
}

26、如果能通过重新排列一个单词的字母来拼出另一个单词，那么这两个单词就是变位词。编写一个名为 is – anagram 的子程序，它接受两个字符串，如果它们是变位词则返回 True。

以下是两种实现方式：

第一种： 


sub is-anagram(Str $word1, Str $word2) {
    return False if $word1.chars != $word2.chars;
    return False if $word1.comb.sort ne $word2.comb.sort;
    True;
}

第二种（更简洁但可能效率稍低）： 


sub is-anagram(Str $word1, Str $word2) {
    return $word1.comb.sort eq $word2.comb.sort;
}

27、编写一个名为has_duplicates的子程序，它接受一个列表或数组，如果其中有任何元素出现不止一次，则返回True。该子程序不应修改原始输入。

以下是几种实现该功能的子程序代码：

使用

repeated

函数：


sub has_duplicates(@array) {
    ?@array.repeated
}

先排序再比较相邻元素：


sub has_duplicates(@array) {
    my @sorted = sort @array;
    for 1..@sorted.end -> $i {
        return True if @sorted[$i] eq @sorted[$i - 1];
    }
    return False;
}

排序后记录前一个元素进行比较：


sub has_duplicates(@array) {
    my @sorted = sort @array;
    my $previous = shift @sorted;
    for @sorted -> $item {
        return True if $item eq $previous;
        $previous = $item;
    }
    return False;
}

使用

unique

函数比较元素数量：


sub has_duplicates(@array) {
    @array.unique.elems != @array.elems;
}

使用哈希表：


sub has_duplicates(@array) {
    my %seen;
    for @array -> $elmt {
        return True if %seen{$elmt}:exists;
        %seen{$elmt} = 1;
    }
    return False;
}

28、如果你的班级有23名学生，那么其中两人同一天生日的概率是多少？你可以通过生成23个随机生日样本并检查是否有重复来估算这个概率。提示：你可以使用rand和int函数生成随机生日。

通过模拟可知，23人的样本中，至少两人同一天生日的概率约为50%。

29、编写一个子程序，读取文件words.txt并构建一个列表，列表中的每个元素对应一个单词。编写此函数的两个版本，一个使用push方法，另一个使用unshift方法。哪个版本运行时间更长？为什么？

unshift版本运行时间更长。因为

unshift

是在数组开头插入元素，Perl需要多次移动数据来重新组织整个数组；而

push

是在数组末尾插入元素，内部操作相对较少。

30、编写一个名为 bisect 的函数，该函数接受一个排序列表和一个目标值，并返回目标值是否在列表中的信息。

以下是实现该功能的代码： 


sub bisect (@word_list, Str $word) {
    my $index = (@word_list.elems / 2).Int;
    return False if $index == 0 and @word_list[$index] ne $word;
    my $found = @word_list[$index];
    if $word lt $found {
        # search the first half
        return bisect @word_list[0..$index-1], $word;
    } elsif $word gt $found {
        # search the second half
        return bisect @word_list[$index+1..*-1], $word;
    }
    True; # if we get there, we've found the word
}

你可以使用如下方式调用这个函数： 


for <a f w e q ab ce> -> $search {
    if bisect [<a b d c e f g>], $search {
        say "found $search";
    } else {
        say "did not find $search";
    }
}

31、如果两个单词互为倒序，则称它们为“倒序对”。编写一个程序，找出words.txt文件中所有的倒序对。

以下是几种实现方式：

方式一：使用二分查找


sub bisect (Str $word, @word_list) { 
    # see the code in the previous exercise
}
my @array = 'words.txt'.IO.lines;
for @array -> $word { 
    my $reverse = $word.flip; 
    my $res = bisect $reverse, @array; 
    say "$word and $reverse form a reverse pair" if $res >= 0;
}
say now - INIT now;

方式二：使用grep和二分查找


say "$_ and $_.flip() form a reverse pair" for @array.grep( { bisect( .flip, @array ) >= 0 } );

方式三：使用哈希查找


my %hash = map { $_ => 1}, 'words.txt'.IO.lines;
for %hash.keys -> $word { 
    my $reverse = $word.flip; 
    say "$word and $reverse form a reverse pair" if %hash{$reverse}:exists;
}
say now - INIT now;

32、如果从两个单词中交替取字母能组成一个新单词，那么这两个单词就“互锁”。编写一个程序，在words.txt文件中找出所有互锁的单词对。提示：不要枚举所有的单词对，因为数量太多了！

以下是解决该问题的程序： 


use lib ".";
use BisectSearch;

my @array = 'words.txt'.IO.lines;
for @array -> $word {
    my ($word1, $word2) = intersplit($word);
    say "$word: $word1, $word2" if bisect($word1, @array) >= 0 and bisect($word2, @array) >= 0;
}

sub intersplit (Str $word) {
    my @letters = $word.comb;
    my $evens = join '', map {@letters[$_] if $_ %% 2}, @letters.keys;
    my $odds = join '', map {@letters[$_] if $_ % 2}, @letters.keys;
    return ($evens, $odds);
}

该程序的思路是，对于单词列表中的每个单词，将其“互拆”为一个包含偶数位字母的字符串和一个包含奇数位字母的字符串，然后检查这些子字符串是否属于该列表。此外，还可以对

intersplit

子程序进行优化，使用一个接受两个参数（一个奇数位字母和一个偶数位字母）的尖块来实现： 


sub intersplit (Str $word) {
    my (@evens, @odds);
    for $word.comb -> $even, $odd {
        push @evens, $even;
        push @odds, $odd;
    }
    return @evens.join, @odds.join;
}

33、对阿克曼函数进行记忆化处理，看看记忆化是否能让该子程序对更大的参数进行求值。提示：不能。

对阿克曼函数进行记忆化处理的代码如下： 


my %ack-memo;
sub mem-ack(Int $m, Int $n) {
    return $n + 1 if $m == 0;
    return mem-ack($m - 1, 1) if $n == 0;
    %ack-memo{"$m;$n"} = mem-ack($m - 1, mem-ack($m, $n - 1)) unless %ack-memo{"$m;$n"}:exists;
    return %ack-memo{"$m;$n"};
}

但实际上，即便使用了记忆化，也不建议尝试对

$m

大于 3 的值运行该函数。因为如果遇到已经计算过的数对对应的阿克曼值，意味着进入了无限循环，所以记忆化阿克曼函数并没有实际意义，无法用更大的参数求值。

34、编写一个名为has – duplicates的函数，该函数接受一个列表作为参数，使用哈希表实现，如果列表中任何对象出现不止一次，则返回True，否则返回False。

可以使用以下代码实现： 


sub has-duplicates(@array) {
    my %seen;
    for @array -> $elmt {
        return True if %seen{$elmt}:exists;
        %seen{$elmt} = 1;
    }
    return False;
}
© 版权声明
文章版权归作者所有，未经允许请勿转载。

相关文章

暂无评论

none
暂无评论...

热门网站

日榜周榜月榜
天气预报

天气预报

中国气象局提供权威的天气预报、气象预警、卫星云图、雷达图等专业服务产品
PaperWord

PaperWord

PaperWord免费论文查重,每天免费查重一篇,一键论文降重达标,一次查重五个报告,不泄露不上传,700万毕业生的选择,毕业安心有保障。更有超实惠论文套餐、限时查重全免活动就等你来体验
AI Ping

AI Ping

MaaSHub
AcFun

AcFun

AcFun是国内首家弹幕视频网站，这里有全网独家动漫新番， 友好的弹幕氛围，有趣的UP主，好玩有科技感的虚拟偶像，年轻人都在用。
有道精品课

有道精品课

有道精品课是网易旗下的知名培优教育品牌，致力于培养未来更具竞争力的优秀少年。提供英语国际、语文人文、数学思维、编程、围棋、象棋等素养类课程，覆盖小学、初中、高中全学段。卓越师资、小班教学、培优体系，用专业方法帮助孩子长效提升
PPT超级市场

PPT超级市场

免费下载PPT模板与PPT作品，提供免费的PPT代做服务，提供一站式PPT(模板、定制、工具、教程)服务，有了它，一切制作PPT的烦恼都将成为过去！
查看完整榜单

热门文章

日榜周榜月榜
📢【產業動向】AI PC 正式抵達！

新📢【產業動向】AI PC 正式抵達！

头像15小时前
7
logo设计｜生物科技与字母的化学反应

logo设计｜生物科技与字母的化学反应

头像4周前
8
WWDC2024苹果有什么新东西？

WWDC2024苹果有什么新东西？

头像3周前
2
查看完整榜单

标签云