☰

使用 bash 命令计算 $a_1 + a_2x + ... + a_nx^{n - 1} (mod 10^9 + 7)$

tag-icon • tag-icon bash scripts
使用 bash 命令计算 $a_1 + a_2x + ... + a_nx^{n - 1} (mod 10^9 + 7)$

我才刚刚开始掌握 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)因为溢出。由于我对命令的了解很少，我无法完全理解如何解决问题。有人可以向我展示问题脚本并附上解释吗？

答案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

那只是多项式，忽略了“mod”因为我不明白那是什么意思。

无论如何，您可以执行类似上述的操作以避免溢出，您将内容通过管道传输到命令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

相关内容