2017-12-03 309 views
2

所以首先帕斯卡三角是這樣的:如何修改我的程序以打印出Pascal的三角形?

Pascal's Triangle

您看到的第一行是零第i行。

當你是一名計算機科學家時,這並不罕見 。

C(N,K)= N:

在帕斯卡三角形每個術語可以與下式的組合來預測!/[k! *(n - k)!],其中「n」是行,「k」是從零到n的任何整數。

所以由此可以得出帕斯卡三角可以用(N,K)組合預測:

Pascal's triangle combinations

這就是你在上圖中看到的。

帕斯卡三角基本上是二項式概率:

(H + T)^ N#你翻轉雙面硬幣「N」次,它的土地上的「正面」或「反面」和你收集的頻率(H + T)^ 3 = 1(H^3)+ 3(H^2)(T)+ 3(H)每個在一組係數中,對於n = 3,我們得到擴展: (T^2)+1(T^3),其中這些係數: 1,3,3,1在帕斯卡三角形的第3行。


我定義了一個階乘,和組合,並能夠與一些循環Perl代碼獲得帕斯卡三角的任何行的 係數號(!):

use strict; 
use warnings; 

# Note the first row is row 0. 
print("\nWhich row of Pascal's triangle to display: "); 
my $row = <STDIN>; # The row that you want to display # This is also n. 
my $terms = $row + 1; # The number of terms is one more than the row number. 

Pascal_Row($row); # Print the Pascal numbers for that row. 

# Function displays the numbers for a row of Pascal's triangle. 
####################################################### 
sub Pascal_Row 
{ 
    my $row = shift; # Row is passed in. 

    for(my $k = 0; $k < $row + 1; $k++) # k alternates, but not the row which is n. 
    { 
     print(combination($row, $k), "\t") # Print each row. 
    } 
    print("\n"); # Print a newline after each time this function is called. 
} 

# This computes the factorial of a number. 
########################################### 
sub factorial 
{ 
    my $number = shift; # argument. 
    my $factorial_number = 1; # initalize the factorial. 

    for(my $i = 1; $i <= $number; $i++) 
    { 
     $factorial_number *= $i; # compute the factorial, by multiplying all terms up to and including number. 
    } 

    return $factorial_number; # Return the factorial number. 
} 

# Computes a matehmatical combination usually denoted as C(n, k) 
# where n is the row number, and k is each item in a row of Pascal's traingle 
sub combination 
{ 
    my($n, $k) = @_; # from input. 

    # This is the mathematical formula for a combination. 
    my $combination_number = factorial($n)/(factorial($k) * factorial($n - $k)); 

    return $combination_number # And returning it. 
} 

如果我運行代碼,並要求楊輝三角的第8行,我得到這樣的:

Which row of Pascal's triangle to display: 8 
1  8  28  56  70  56  28  8  1 

這對楊輝三角的第8行完全正確的。如果我從第0行循環到Pascal三角形的第8行,我會得到所有正確的Pascal三角形行,但它看起來不像一個三角形(它看起來更像一個盒子),所以我怎麼修改我的代碼來調整縮進。

如果我想要顯示8行Pascal三角形,我該如何決定縮進第一行多少?我怎樣才能做出一個「三角形」?

+1

你知道你要多少行有,這意味着你知道你是從底部多少行:下面

整個劇本中給出。每行的第一個數字在下一行的第一個數字和第二個數字之間的一半,所以它必須被用於行上數字的間距的一半。用那個武裝......乘以! – hobbs

+0

在這種情況下,我不應該用製表符分隔行上的每個係數嗎? – xyz123

+0

是的,你會遇到一個問題,一直沿着tabstops。我會建議看看'printf'的固定寬度輸出:) – hobbs

回答

2

這是因爲數事項佈局的變化的寬度棘手。

每行需要縮進行中數字間距的一半,適當地相乘(最後一行爲零,第一行爲1) - 也就是說,如果數字本身都是相等的寬度。

但事實並非如此,除了前幾行外;數字需要不同的空間。一種補救措施是使用固定寬度的數字,並使用該寬度調整縮進和分隔。

首先計算所有行,以便可以找到數字的最大寬度。

use warnings; 
use strict; 
use feature 'say'; 
use List::Util qw(max); 

my $max_row = (shift || 8); 

my @rows = map { pascal_row($_) } 0..$max_row-1; 

my $max_num_wd = max map { length } @{$rows[-1]}; 
my $pad = 1; # choice (must be non-zero) 
my $sep  = ' ' x ($max_num_wd + 2*$pad); 
my $lead_sp = ' ' x ($max_num_wd + $pad); 

for my $n (0..$#rows) { 
    say $lead_sp x ($max_row-1-$n), 
     join $sep, map { sprintf "%${max_num_wd}d", $_ } @{$rows[$n]}; 
} 

sub pascal_row { 
    my ($row) = @_; 
    return [ map { n_over_k($row, $_) } 0..$row ]; 
} 

sub n_over_k { 
    my ($n, $k) = @_; 
    return factorial($n)/(factorial($k) * factorial($n - $k)); 
} 

sub factorial { 
    my ($n) = @_;   
    my $fact = 1; 
    $fact *= $_ for 2..$n; 
    return $fact; 
} 

這會打印正確的佈局。 $pad是一個任意整數,用於超出最大數字寬度的額外空間,用於縮進和分隔;它必須> 0來協調它們。 (分離需要居中一定數量的空間的左側和右側的行中的上方,因而2.因子)


原始代碼,印刷爲它計算以便$max_num_wd是通過手工設定提前

# (includes and subs same as above except for List::Util)  
my $max_row = (shift || 8); 

my $max_num_wd = 4; # maximum width of numbers 
my $pad  = 1; # choice (non-zero) 
my $sep  = ' ' x ($max_num_wd + 2*$pad); 
my $lead_sp = ' ' x ($max_num_wd + $pad); 

for my $n (0..$max_row-1) { 
    my @row = @{ pascal_row($n) }; 
    say $lead_sp x ($max_row-1-$n), 
     join $sep, map { sprintf "%${max_num_wd}d", $_ } @row; 
} 

這會打印一個正確的佈局,其編號最多爲4位寬,或者需要調整$max_num_wd

+0

感謝您的解釋。你的修改工作很好! – xyz123

3

左對齊三角形:

my $MAX_VAL_SIZE = 5; 

for my $n (0...$N) { 
    my @row; 
    for my $k (0..$n) { 
     push @row, C($n, $k); 
    } 

    say join " ", map sprintf("%*d", $MAX_VAL_SIZE, $_), @row; 
} 

中心三角形:

sub center { 
    my ($n, $s) = @_; 
    my $pad_len = $n - length($s); 
    my $pad_len_l = int($pad_len/2); 
    my $pad_len_r = $pad_len - $pad_len_l; 
    return (" " x $pad_len_l) . $s . (" " x $pad_len_r); 
} 

my $MAX_VAL_SIZE = 5; 

for my $n (0...$N) { 
    my @row; 
    for my $k (0..$n) { 
     push @row, C($n, $k); 
    } 

    my $row = join " ", map center($MAX_VAL_SIZE, $_), @row; 
    say center(($N+1)*($MAX_VAL_SIZE+2)-2, $row); 
} 
+0

你能解釋一下這一點嗎?我的思想完全被吹掉了! – xyz123

+0

'center(N,STRING)'將字符串填充到N個字符,將填充字符拆分爲字符串的兩邊以居中。所以'中心(5,1)'返回'␠␠1␠␠'。這是針對每個數字以及整個行進行的。 – ikegami

2

這裏是做的另一種方式:

use strict; 
use warnings; 

sub fact { 
    my $n = shift; 
    return 1 if $n < 1; 
    return $n * fact($n - 1); 
} 

sub n_over_k { 
    my $n = shift; 
    my $k = shift; 
    return fact($n)/(fact($k) * fact($n - $k)); 
} 

sub pascal_row { 
    my $n = shift; 
    return map { n_over_k($n - 1, $_) } (0 .. $n - 1); 
} 

my $n = shift || 8; 

# $maxw is the first odd width where the biggest number will fit 
my $max = 0; 
map { $max = $_ if $_ > $max } pascal_row($n); 
my $maxw = length('' . $max); 
$maxw += ($maxw + 1) % 2; 

# Print the Pascal´s triangle 
foreach my $i (1..$n) { 
    print ' ' x (($maxw + 1) * ($n - $i)/2); 
    foreach my $j (pascal_row($i)) { 
    printf "%${maxw}d ", $j; 
    } 
    print "\n"; 
} 

它怎麼辦?在打印的最大數量適合的第一個奇數寬度內適合每個數字。這是因爲數字是用空格分隔的,並且會使每個寬度均勻(並且對於奇數三角形行可以將其整除)。然後使用printf來格式化數字。例如%5d將在5個字符內對齊數字。在除了最後一行之外的每行之前使用' ' x N生成一串N空格的必要空格。

的8帕斯卡三角:13

# pascal.pl 8 
       1 
       1 1 
      1 2 1 
      1 3 3 1 
     1 4 6 4 1 
     1 5 10 10 5 1 
    1 6 15 20 15 6 1 
    1 7 21 35 35 21 7 1 

楊輝三角:

# pascal.pl 13 
          1 
         1 1 
         1 2 1 
        1 3 3 1 
        1 4 6 4 1 
       1 5 10 10 5 1 
       1 6 15 20 15 6 1 
      1 7 21 35 35 21 7 1 
      1 8 28 56 70 56 28 8 1 
     1 9 36 84 126 126 84 36 9 1 
     1 10 45 120 210 252 210 120 45 10 1 
    1 11 55 165 330 462 462 330 165 55 11 1 
    1 12 66 220 495 792 924 792 495 220 66 12 1 
1

您可以生成無任何組合學公式的三角形。

這樣做的原因是這是最有效的方法。

基本思想是採用觀察,下一行 行的值是位於上面的2個元素的總和。

該解決方案也是如何使用數組的 (引用)的一個很好的示例。

一個有趣的特點是,縮進從 中間元計算的最後一行(以最大的值)英寸

要提供三角形的美麗外觀,單元格大小必須是偶數。 「基本」縮進是這個尺寸的一半。 每行的實際縮進是這個基本尺寸,乘以相應的 數字,從行索引和總行數得出。

use strict; 
use warnings; 
use feature qw(say); 
use POSIX qw(ceil); 

my $rowCnt = 14;  # How many rows 
say "Pascal Triangle with $rowCnt rows:"; 
# Rows container, filled with a single row (containing single 1) 
my @rows = ([ 1 ]); 
my ($lastRow, $row, $ind); 
# Generate/add further rows 
for ($ind = 1; $ind < $rowCnt; $ind++) { 
    $lastRow = $rows[$#rows]; # Last row gathered so far 
    push(@rows, getNextRow($lastRow)); 
} 
$lastRow = $rows[$#rows]; 
# Middle elem. of the last row 
my $midElem = $$lastRow[($rowCnt - 1)/2]; 
# No of digits + separator, rounded up to even 
my $elemSize = ceil((length($midElem) + 1)/2) * 2; 
my $shf = $elemSize/2; # Shift size for a sigle step 
# Print rows 
for ($ind = 0; $ind < $rowCnt; $ind++) { 
    my $row = $rows[$ind]; 
    my $spc = $shf * ($rowCnt - $ind - 1); 
    printRow($spc, $row, $elemSize); 
} 

sub getNextRow { # Create the next row and return the reference to it 
    my $lastRow = $_[0]; # Read param 
    my @row = (1); # Start the new row from a single 1 
    for (my $i = 0; $i < $#$lastRow; $i++) { 
    push(@row, $$lastRow[$i] + $$lastRow[$i + 1]); 
    } 
    push(@row, 1); # Add terminating 1 
    return \@row;  # Result - reference to the created row 
} 

sub printRow {  # Print a row of the triangle 
    my ($leadSpc, $row, $elemSize) = @_; # Read params 
    # Leading spaces and the initial element (always 1) 
    printf("%s1", ' ' x $leadSpc); 
    # Print the rest of the row 
    for (my $i = 1; $i <= $#$row; $i++) { 
    printf("%*d", $elemSize, $$row[$i]); 
    } 
    print("\n"); 
}