1

二分探索を実装しようとしています。これは私のコードです: 

#!/usr/bin/perl
#use strict;
use warnings;

@array = (1..100);
$number = <STDIN>;
$low = 0;
$high = $#array;

while($low < $high){
    print "Searcing $low ---- $high \n";
    $mid = $low + ($high - $low)/2;
    if($array[$mid] == $number){
        print "Found in index:" . $mid;
        last;
    }
    elsif($array[$mid] < $number){
        $low = $mid + 1;
    }
    else{
        $high = $mid - 1;
    }   
}

しかし、それは単純な実装ですが (少なくとも Java では可能です)、機能しません。
分割時にfloat値を取得して検索できないようです。入力として提供する5と、ゴミが発生します。 

5  
Searcing 0 ---- 99  
Searcing 0 ---- 48.5  
Searcing 0 ---- 23.25  
Searcing 0 ---- 10.625  
Searcing 0 ---- 4.3125  
Searcing 3.15625 ---- 4.3125

整数を使用して配列にインデックスを付けるにはどうすればよいですか?
また、コメントを外すuse strictと、次のエラーが発生します。彼らはどういう意味ですか？ 

Global symbol "@array" requires explicit package name at D:\Development\Perl\chapter3\binarySearch.pl line 6.  
Global symbol "$number" requires explicit package name at D:\Development\Perl\chapter3\binarySearch.pl line 9.  
Global symbol "$low" requires explicit package name at
4

6 に答える 6

6 
my $int = int 5 / 2;
print $int;

プリント 2.

于 2013-04-10T20:38:43.687 に答える
3

2つの難解な解決策。本当に退屈か何かでない限り、実際にはこれらを使用しないでください。

  1. use integer-- Perl にすべての数値を整数として扱わせるプラグマ。ローカルにスコープできるため、プログラム内のすべてのデータを台無しにすることはありません

    while($low < $high){
    print "Searcing $low ---- $high \n";
    {
        use integer;
        $mid = $low + ($high - $low)/2;
    }
    if($array[$mid] == $number){
        print "Found in index:" . $mid;
        last;
    }
    elsif($array[$mid] < $number){
        $low = $mid + 1;
    }
    else{
        $high = $mid - 1;
    }   
}

  2. Perl にはいくつかの特別な変数$=, $-, があり、$%それらに何を割り当てても、整数値のみを保持します。それらを直接使用する

    $- = $low + ($high - $low) / 2;
if ($array[$-] == $number) { ...

    または中間体として

    my $mid = $- = $low + ($high - $low) / 2;
if ($array[$mid] == $number) { ...

    このような魔法の変数の使用は、コード ゴルフや同僚のイライラには便利ですが、それ以外はあまり役に立ちません。

于 2013-04-11T04:55:42.163 に答える
2

コードにはかなりの問題があります。

  • strictを無効にしました。

    おそらく次の問題のためです。

  • myまたはourまたはを使用して、変数を宣言していませんuse vars。

    our @array = 1..100;
use vars qw'$mid $low $high';
my $number = <STDIN>

  • オーバーフローについて心配しすぎます。これは C ではありません。

    数値が整数をオーバーフローする場合は、浮動小数点数になります。

    my $mid = $low + ($high - $low)/2;

    おそらく次のようにする必要があります。

    my $mid = ($high + $low)/2;

  • あなたは除算から整数を期待していました。

    my $mid = ($high + $low)/2;

    本当に整数が必要な場合は、 を使用してintください。

    my $mid = int( ($high + $low)/2 );

  • の末尾から改行を削除しませんでした$number

    chomp($number);

  • オフ バイ ワン エラーがあります。

    while($low < $high){

    本当のはず

    while($low <= $high){

    これは本当にあなたの主な問題です。

#! /usr/bin/env perl
use strict;
use warnings;

my @array = 1..100;
my $number = <STDIN>;
chomp $number;
my $low = 0;
my $high = $#array;

while($low <= $high){
    my $mid = int( ($high + $low)/2 );
    printf "Searching %2d .. (%2d) .. %2d\n", $low, $mid, $high;
    if($array[$mid] == $number){
        print "Found $number at index mid $mid\n";
        last;
    }elsif($array[$mid] < $number){
        $low = $mid + 1;
    }else{
        $high = $mid - 1;
    }
}

ただし、それは実際には Perlish ではありません。

#!/usr/bin/perl
use strict;
use warnings;
use List::MoreUtils qw'first_index';

my @array = 1..100;
my $number = <STDIN>;
chomp $number;

my $index = first_index { $_ == $number } @array;
print "Found $number at index ", $index if $index != -1;

またはもっと奇妙に

#! /usr/bin/env perl
use strict;
use warnings;

my @array = 1..100;
my $number = <STDIN>;
chomp $number;

my $char = join '', map chr, @array;

my $index = index $char, chr $number;
print "Found $number at index $index\n" if $index != -1;

UVこれは、 max またはの小さい方までの数値で機能します(2 ** 72) - 1。
つまり、64 ビット ビルドでは 18,446,744,073,709,551,615、32 ビット ビルドでは 4,294,967,295 です。

于 2013-04-11T19:17:35.970 に答える
2

関数intを使用する必要があります。

それとは別に、変数をスコープするuse strict;ために使用する必要があります。myこれにより、見逃す可能性のあるエラーがキャッチされます。次のように宣言するだけです。

my @array = (1..100);
chomp(my $number = <STDIN>);
my $low = 0;
my $high = $#array;

my $mid = int ($low + ($high - $low)/2);

入力から改行を削除するために、chompも使用することを検討してください。

于 2013-04-10T20:43:29.050 に答える