INNOVATION
LAB

选拔考试C语言试题提示

(1)代数式处理

  注意:输入的表达式只有x,+,-,*,/,(,)没有数字和其它字符

a)  函数数值方法一:后缀表达式

Step1:保存输入的表达式到字符数组,此表达式中所有的运算符号都在两数字的中间,因此叫做中缀表达式

Step2:用输入的数值,替换表达式中的x,得到一个代数式

Step3:将中缀表达式转化为后缀表达式

我们把平时所用的标准四则运算表达式,即“9+(3-1)*3+10/2"叫做中缀表达式。因为所有的运算符号都在两数字的中间,现在我们的问题就是中缀到后缀的转化。

中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1-3*+ 10 2/+”

·      规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于找顶符号(乘除优先加减)则栈顶元素依次出找并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

下面我们来具体看看这个过程。

1. 初始化一空栈,用来对符号进出栈使用。

2. 第一个字符是数字9,输出9,后面是符号“+”,进

3. 第三个字符是“(”,依然是符号,因其只是左括号,还未配对,故进栈。

4. 第四个字符是数字3,输出,总表达式为9 3,接着是“-”进栈。

5. 接下来是数字1,输出,总表达式为9 3 1,后面是符号“)”,此时,我们需要去匹配此前的“(”,所以栈顶依次出栈,并输出,直到“(”出栈为止。此时左括号上方只有“-”,因此输出“-”,总的输出表达式为9 3 1 -

6. 接着是数字3,输出,总的表达式为9 3 1 - 3 。紧接着是符号“*”,因为此时的栈顶符号为“+”号,优先级低于“*”,因此不输出,进栈。

7. 之后是符号“+”,此时当前栈顶元素比这个“+”的优先级高,因此栈中元素出栈并输出(没有比“+”号更低的优先级,所以全部出栈),总输出表达式为 9 3 1 - 3 * +.然后将当前这个符号“+”进栈。也就是说,前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”,而下图中的栈底(也是栈顶)的“+”是指“9+(3-1)*3+”中的最后一个“+”

8. 紧接着数字10,输出,总表达式变为9 3 1-3 * + 10

9. 最后一个数字2,输出,总的表达式为 9 3 1-3*+ 10 2

10. 因已经到最后,所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1-3*+ 10 2/+

·      从刚才的推导中你会发现,要想让计算机具有处理我们通常的标准(中缀)表达式的能力,最重要的就是两步:

1.    将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。

2.   将后缀表达式进行运算得出结果(栈用来进出运算的数字)。

整个过程,都充分利用了找的后进先出特性来处理,

Step4:计算后缀表达式的值

后缀表达式:9 3 1-3*+ 10 2/+

·      规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

下面是详细的步骤:

1. 初始化一个空。此桟用来对要运算的数字进出使用。

2. 后缀表达式中前三个都是数字,所以931进栈。

3. 接下来是减号“-”,所以将栈中的1出栈作为减数,3出栈作为被减数,并运算3-1得到2,再将2进栈。

4. 接着是数字3进栈。

5. 后面是乘法“*”,也就意味着栈中32出栈,23相乘,得到6,并将6进栈。

6. 下面是加法“+”,所以找中69出找,96相加,得到15,将15进栈。

7. 接着是102两数字进栈。

8. 接下来是符号因此,栈顶的210出栈,102相除,得到5,将5进栈。

9. 最后一个是符号“+”,所以155出找并相加,得到20,将20进栈。

10. 结果是20出栈,栈变为空。

方法二:直接用中缀表达式求值

Step1:获取输入表达式,存到字符数组L0

Step2:对输入表达式进行处理,先找到L0中的第一个左括号,将左括号和右括号间的表达式转存到另一个字符数组L10[]中,若后面还有第二个左括号,则继续将左括号和右括号间的表达式转存到另一个字符数组L11[]中,依次类推,直到L0的结束

Step3:对第一层扩后内的表达式,比如L10[]L11[]进行处理,得到第二层括号内的内容

Step4:再得到第三层或者更多层的括号

Step5:当取到最内层括号内的内容时,代入x值进行运算,然后用算出的值替换上一层中括号内的内容

b)  导函数数值方法一:根据某点导函数的定义,用左右极限相等法

数学原理:

求解步骤:

Step0:由a)已经得到f(x0)的值,先取h=1.0

Step1:分别计算f(x0+h)f(x0-h)

Step2:计算ds1=( f(x0+h)- f(x0))/h,ds2=(f(x0)- f(x0-h))/h

Step3:若|ds1-ds2|<1.0*10-6,则得到导函数值f’(x0)=ds1=ds2;否则h=h/2,重新回到Step1;

导函数数值方法二:根据导函数定义,单方向迭代逼近

Step0a)已经得到f(x0)的值,先取h=1.0ds1=0

Step1:计算f(x0+h),取ds2= (f(x0+h)-f(x0))/h

Step2:若|ds1-ds2|<1.0*10-6,则得到导函数值f’(x0)=ds2;否则ds1=ds2h=h/2,重新回到Step1;

导函数数值方法三:利用求导公式,算出导函数表达式,再代入x值计算

Step1:对输入表达式进行化简,得到类似1/(x+1),x*x*x+x*x+1等分式或多项式

Step2:利用求导公式求导

Step3:代入x值计算

  方法三由于输入表达式情况较多,比较难实现,若要用此方法,可简化成输入仅为多项式。

(2)小岛面积

  注意:输入若不会处理,可先定义一个二维数组,保存矩阵的值,用作测试。

理解题目本身意思,其实是要给出矩阵中元素0应该满足的条件。

a)基本条件

Ø   0所在的行,0的左边和右边必须有1

Ø   0所在的列,0的上面和下面必须有1

  b)深层条件

Ø   要构成小岛,必须要有1围成的圈

所以,解题思路就是:

遍历所有的行和列,记录该行或列,最左面和最右面(或者最上面和最下面)1的坐标,先看能否围成一个大圈。若能围成大圈,很简单,圈内满足基本条件的0,即为小岛。若不能围成大圈,再找里面是否有小圈,没有小圈就没有小岛,有小圈,计算小圈内满足基本要求的0的个数即为小岛面积。


会员登录
登录
回到顶部