вычислить $ a_1 + a_2x +… + a_nx ^ {n - 1} (mod 10 ^ 9 + 7) $ с помощью команд bash

Я только начинаю осваивать bash и у вас проблемы с пониманием того, как собрать программу для следующей задачи:

Формат ввода: первое число в input.txt - 0 <= x <= 10 ^ 9, затем идет неопределенное количество 0 <= a_1, ..., a_n <= 10 ^ 9, все числа разделены новыми строками.

Выведите ответ для $ a_1 + a_2x + ... + a_nx ^ {n - 1} (mod 10 ^ 9 + 7) $

Прежде всего, я не могу понять, как читать переменную по переменной, кроме использования $ (cat input.txt) или $ (head -1 input.txt) , поэтому я не понимаю, как правильно вводить переменные. Во-вторых, мы не можем использовать тупое возведение в степень ($ x ** $ i) из-за переполнения. Из-за моего скудного знания команд я не могу полностью понять, как решить эту проблему. Может ли кто-нибудь показать мне сценарий проблемы с объяснением?

0
задан 8 December 2020 в 22:01

1 ответ

Вы можете сделать что-то вроде этого:

# Get x from first line in the file
x=`head -n 1 input.txt`
echo x = $x
# Get number of lines in the file
n=`cat input.txt | wc -l`
((nn=n-2))
# We will loop over i starting with i=0 so then x_to_power_i starts at 1
x_to_power_i=1
sum=0
for i in `seq 0 $nn` ; do
    # Show what we have now
    echo i = $i x_to_power_i = $x_to_power_i
    # Get a_i value
    ((ii=i+2))
    a_i=`cat input.txt | head -n $ii | tail -n 1`
    echo a_i = $a_i
    # Calculate current term and add it to sum
    tmp=`echo "$sum + $a_i*$x_to_power_i" | bc -l`
    sum=$tmp
    echo sum = $sum
    # Update x_to_power_i for next i
    tmp=`echo "$x_to_power_i*$x" | bc -l`
    x_to_power_i=$tmp
done
# Show final result
echo Final sum = $sum

Это всего лишь полином, игнорируя "мод", поскольку я не понимаю, что это значит.

В любом случае, вы можете делать подобные вещи, чтобы избежать переполнения, вы передаете данные команде bc (bc — язык калькулятора произвольной точности — см. man bc).

Редактировать: вот еще один вариант, перебирающий непосредственно содержимое файла вместо использования seq:

# Get x from first line in the file
x=`head -n 1 input.txt`
echo x = $x
# Get number of lines in the file
n=`cat input.txt | wc -l`
# Create a new file with all except first line
((nn=n-1))
tail -n $nn input.txt > tmpfile.txt
# We will loop over i starting with i=0 so then x_to_power_i starts at 1
x_to_power_i=1
sum=0
i=0
for a_i in `cat tmpfile.txt` ; do
    # Show what we have now
    echo i = $i x_to_power_i = $x_to_power_i
    echo a_i = $a_i
    # Calculate current term and add it to sum
    tmp=`echo "$sum + $a_i*$x_to_power_i" | bc -l`
    sum=$tmp
    echo sum = $sum
    # Update x_to_power_i for next i
    tmp=`echo "$x_to_power_i*$x" | bc -l`
    x_to_power_i=$tmp
((i=i+1))
done
# Show final result
echo Final sum = $sum
1
ответ дан 8 December 2020 в 19:39

Другие вопросы по тегам:

Похожие вопросы: