Блог

Я пытаюсь создать программу, в которой перечислены все каталонские числа, меньшие или равные аргументу в bash-скрипте. Это то, что у меня есть в настоящее время, но оно выдает мне ошибку stackoverflow (я считаю, что ошибка должна быть в цикле for, но я не могу понять почему). Я создал эту программу на Java, и она работает, поэтому я думаю, что это должна быть какая-то синтаксическая ошибка?

 #!/usr/bin/env bash
pcat=0

Cat() {

res=0

    if [ $1 -le 1 ]
    then
        echo 1
        return 1
    fi

    for ((i=0; i<$1; i  ))
    do
        var1=$(($1-($i 1)))
        call1=$(Cat $i)
        call2=$(Cat $var1)

        res=$(( res call1 call2 ))
    done

echo ${res}
return res

}


while [ $pcat -lt $1 ]
do
    Cat $pcat

    pcat=$((pcat 1))
done
  

Строка, в которой вы это делаете return res , неверна, return может иметь дело только с числами и числом меньше 128 в целом.

Предполагая, что вы имели в виду return $res , скрипт будет запущен.

Мне удалось заставить программу работать с кодом, похожим на ваш:

 #!/bin/bash
catalan() {
    local n=$1
    #echo "called with $n" >amp;2

    if (( n <= 1 )); then
        res=1
    else
        res=0
        for ((i=0; i<n; i  ))
        do
            var1=$(( n-i-1 ))
            call1=$(catalan $i)
            call2=$(catalan $var1)
            res=$(( res call1*call2 ));
            #echo ":$i:$var1: result Call1:$call1: and Call2:$call2: $res" >amp;2
        done
    fi
    #echo "result is ${res}" >amp;2
    echo "$res"
}

n=$1
until  (( pcat > n ))
do     catalan "$((pcat  ))"
done


echo "all was done"
  

Вторая проблема заключалась в том, что значения Call1 и Call2 нужно умножать, а не добавлять. Изменено res call1 call2 на:

 res=$(( res call1*call2 ))
  

Но результирующий код был очень медленным. Просто для вычисления десятого (10) каталонского числа код занял 16 секунд.

Совершенно новая программа, которая хранит значения внутри одного массива : catarray .

Поскольку это:

 #!/bin/bash

# some initial values to jump start the code:
catarray=( 1 1 2 5 )

#############################################################################
catalan(){
    #echo "making call for $1" >amp;2
    local n=$1
    # ${#catarray[@]} is the count of values in catarray (last index   1).
    # if the number n to be found is not yet in the array of values of
    # catarray then we need to calculate it. Else, we just print the value.
    if (( n >= ${#catarray[@]} )); then
        #echo "$n is bigger than ${#catarray[@]}" >amp;2
        # this is a new number, lets loop up till we
        # fill the array just up to this value
        for (( i=${#catarray[@]};i<=n;i  )); do
        #echo "fill index $i in array" >amp;2
        # calculate the sum of all terms for catalan of $n.
            for(( j=0;j<i;j   )); do
                (( catarray[i]  = catarray[j] * catarray[i-j-1] ))
                #echo "done math in $i for $j with ${catarray[j]} *
                #echo "* ${catarray[i-j-1]} = ${catarray[i]}"
            done
        done
    fi
    # After making the math or else we just print the known value.
    #printf 'result of catalan number is %sn' "${catarray[n]}"
}
#############################################################################
catalan "$1"

printf '%s, ' "${catarray[@]}"; echo
  

Который выполнит десятое (10) каталонское число всего за 4 миллисекунды.

Было включено много эхо-сигналов, чтобы «увидеть», как работает программа. Вы можете отменить их кавычки.

Однако существует ограничение: числа в bash должны соответствовать 64 битам (для 64-разрядных компьютеров) или быть меньше (2 ^ 63-1). Это делает наибольшее возможное число в каталонском языке 35-м.

 $ catalan 35
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900,  
2674440, 9694845, 35357670, 129644790, 477638700, 1767263190,  
6564120420, 24466267020, 91482563640, 343059613650, 1289904147324,  
4861946401452, 18367353072152, 69533550916004, 263747951750360,  
1002242216651368, 3814986502092304, 14544636039226909,  
55534064877048198, 212336130412243110, 812944042149730764,  
3116285494907301262
  

Но для этого потребуется всего ~ 20 миллисекунд.