方程求根计算器实验报告一C--版.docx

计算方法实验

题目：
班级：
学号：
姓名：
19

计算方法与实习实验报告
目录
计算方法实验 1
1 实验目的 3
2 实验步骤 3
2.1环境配置： 3
2.2添加头文件 3
2.3主要模块 3
3 代码 4
3.1主程序部分 4
3.2多项式方程部分 4
3.3核心算法部分 7
3.4数据结构部分 11
4运行结果 16
4.1二分法运行结果 16
4.2牛顿迭代法运行结果 17
4.3割线法运行结果 18
边界情况调试 18
5总结 20
输入输出 20
二分法 20
牛顿迭代法 20
割线法 20
6参考资料 20

1 实验目的
1. 通过编程加深二分法、牛顿法和割线法求解多项式方程的理解
2. 观察上述三种方法的计算稳定性和求解精度并比较各种方法利弊
2 实验步骤
2.1环境配置：
VS2013，C++控制台程序
2.2添加头文件
#include "stdio.h"
#include "stdlib.h"
#include "stdafx.h"
2.3主要模块
程序一共分成三层，最底层是数据结构部分，负责存储数据，第二层是交互部分，即多项式方程部分，负责输入输出获得数据，最上层是核心的算法部分，负责处理已获得的数据。
主函数负责获取方程系数并显示，算法和方程作为后台程序，顺序表作为存储手段。
3 代码
3.1主程序部分
// squencelistandlinklist1.cpp : 定义控制台应用程序的入口点。
//
#include "stdio.h"
#include "stdlib.h"
#include "stdafx.h"
#include "squencelist.h"
#include "equation.h"
#include<iostream>
///////////////////////////////////主程序//////////////////////////////////////
int _tmain(int argc, _TCHAR* argv[])
{
GetEquation();
ShowMenu();
return 0;
}
3.2多项式方程部分
l 方程部分头文件
#ifndef _EQUATION_H
#define _EQUATION_H

#include "squencelist.h"
#include "stdio.h"
#include "stdlib.h"

extern int highestx;
extern sequenlist *B;
extern sequenlist *D;

double Function(sequenlist *B, double x);
void GetEquation(void);
void ShowMenu(void);
void printfunction(sequenlist *A);
sequenlist Derivative(sequenlist *A, int highestx);

#endif

l 方程部分CPP文件
#include "stdafx.h"
#include "equation.h"
#include "math.h"
#include "algorithm.h"
#include "squencelist.h"

//全局变量
int highestx=0;
sequenlist *B;
sequenlist *D;

//////////////////////////多项式函数///////////////////////////
double Function(sequenlist *A,double x)
{
double f = 0.00;
int i;
for (i = 1; i <= A->last; i++)
f = f + A->data[i] * pow(x, A->last - i);
return f;
}

////////////////////////多项式函数系数/////////////////////////
void GetEquation(void)
{
int j = 0;
int x = 0;

B = InitList();

cout << "方程最高项次数（如y=x^3最高项次数为3）：" << endl;
cin >> highestx;

cout << "输入方程系数,输入00结束（如y=x^2+2x+1输入1 2 1 00）:" << endl;
cin >> x;
while (x != 00)
{
for (j = 1; j <= highestx + 1; j++)
{
if (!Insert(B, x, j))exit(0);
cin >> x;
}

}
j = 1;
printfunction(B);
}

//////////////////////////显示交互/////////////////////////////
void ShowMenu(void)
{
int x;
double a, b, ex, ef, res, x0,x1;
cout << "选择求解方程根的方法：" << endl;
cout << "1.二分法求解" << endl;
cout << "2.牛顿迭代法求解" << endl;
cout << "3.割线法求解" << endl;
cin >> x;

switch (x)
{
case 1:
cout << "请输入区间上下限（如【a,b】输入a b）：" << endl;
cin >> a >> b;
cout << "请输入根的容许误差和函数的容许误差（若只有一个误差则另一项为0）：" << endl;
cin >> ex >> ef;
res = Dichotomy(a,b,ex,ef);
break;
case 2:
cout << "请输入初始值x0：" << endl;
cin >> x0;
cout << "请输入根的容许误差和函数的容许误差（若只有一个误差则另一项为0）：" << endl;
cin >> ex >> ef;
res = Newtonsmethod(x0, ex, ef);
break;
case 3:
cout << "请输入初始值x0,x1：" << endl;
cin >> x0 >> x1;
cout << "请输入根的容许误差和函数的容许误差（若只有一个误差则另一项为0）：" << endl;
cin >> ex >> ef;
res = Cutmethod(x0, x1, ex, ef);
break;
default:break;
}

}

////////////////////////打印输出函数///////////////////////////
void printfunction(sequenlist *A)
{
int i;
cout << "f=";
for (i = 1; i < A->last; i++)
{
if (A->data[i+1] < 0)
cout << A->data[i] << "*" << "x^" << A->last - i;
else cout << A->data[i] << "*" << "x^" << A->last - i << "+";
}
cout << A->data[i] << endl;

}

//////////////////////////函数微分/////////////////////////////
sequenlist Derivative(sequenlist *A, int highestx)
{
int i;
D = InitList();
for (i = 1; i <= A->last; i++)
Insert(D,( A->data[i] * (A->last - i)), i);
D->last = A->last - 1;
return *D;
}
3.3核心算法部分
l 算法部分头文件
#ifndef _ALGORITHM_H
#define _ALGORITHM_H

#include "stdio.h"
#include "stdlib.h"

int Judge(double x1, double x0, double e);
double Dichotomy(double xa, double xb, double ex, double ef);
double Newtonsmethod(double x0, double ex, double ef);
double Cutmethod(double x1, double x0, double ex, double ef);
#endif

l 算法部分CPP文件
#include "algorithm.h"
#include "stdafx.h"
#include "squencelist.h"
#include "equation.h"

//////////////////////////误差判别////////////////////////////
inline int Judge(double x1, double x0, double e)
{
if (e == 0)
return 0;
if (x1 == 0)
{
if (fabs(x0) < e)return 1;
else return 0;
}
if (x0 == 0)
{
if (fabs(x1) < e)return 1;
else return 0;
}
if (fabs(x1 - x0) < e)
return 1;
else return 0;

}

//////////////////////////二分法////////////////////////////
double Dichotomy(double xa, double xb, double ex, double ef)
{
cout << "///////////////////二分法///////////////////" << endl;

double xn = 0, fn = 0, fa = Function(B, xa), fb = Function(B, xb);
double a, b;
int n = 1, flag = 0;
a = xa;
b = xb;
cout << "二分次数" << "\t" << 'x' << "\t\t" << "f(x)" << endl;
if (fa*fb > 0)
{
cout << "无法使用二分法" << endl;
flag = 1;
}

while (1)
{
if (fa == 0)
{
xn = xa;
cout << n++ << "\t\t" << xn << "\t\t" << Function(B, xn) << endl;
break;
}
if (fb == 0)
{
xn = xb;
cout << n++ << "\t\t" << xn << "\t\t" << Function(B, xn) << endl;
break;

}

xn = (a + b) / 2;
fn = Function(B, xn);
cout << n++ << "\t\t" << xn << "\t\t" << Function(B, xn) << endl;

if (fn == 0)break;
if (fn*fa < 0)
{
b = xn;
flag = (Judge(a, b, ex) || Judge(fn, 0, ef));

}
else if (fn*fb < 0)
{
a = xn;
flag = (Judge(a, b, ex) || Judge(fn, 0, ef));

}
if (flag)break;
}
return xn;
}

//////////////////////////牛顿迭代法////////////////////////////
double Newtonsmethod(double x0, double ex, double ef)
{
double xn = 0, fn = 0, dfn = 0;
int n = 1, flag = 0;
cout << "///////////////////牛顿迭代法///////////////////" << endl;
cout << "迭代次数" << "\t" << "x" << "\t\t" << "f(x)" << endl;
*D = Derivative(B, highestx);
fn = Function(B, x0);
dfn = Function(D, x0);
if (fabs(fn) < ef)flag = 1;
while (1)
{
if (dfn == 0)
{
cout << "导数为零" << endl;
break;
}
xn = x0 - fn / dfn;
fn = Function(B, x0);
dfn = Function(D, x0);
flag = (Judge(xn, x0, ex) || Judge(fn, 0, ef));
if (flag)break;
x0 = xn;
cout << n++ << "\t\t" << xn << "\t\t" << Function(B, xn) << endl;
if (n > 3000)
{
cout << "迭代失败" << endl;
return 0;
}
}
return xn;
}

//////////////////////////割线法////////////////////////////
double Cutmethod(double x1, double x0, double ex, double ef)
{
double xn, fn, f0, f1;
int n = 1, flag = 0;
cout << "///////////////////割线法///////////////////" << endl;
cout << "迭代次数" << "\t" << "x" << "\t\t" << "f(x)" << endl;
*D = Derivative(B, highestx);
f0 = Function(B, x0);
f1 = Function(B, x1);
if (fabs(f0) < ef)
{
cout << n++ << "\t\t" << x0 << "\t\t" << Function(B, x0) << endl;
return x0;
}
if (fabs(f1) < ef)
{
cout << n++ << "\t\t" << x1 << "\t\t" << Function(B, x1) << endl;
return x1;
}
if (Judge(x1, x0, ex))
{
cout << n++ << "\t\t" << x1 << "\t\t" << Function(B, x1) << endl;
return x1;
}

while (!flag)
{
xn = x1 - f1*(x1 - x0) / (f1 - f0);
fn = Function(B, xn);
flag = (Judge(xn, x1, ex) || Judge(fn, 0, ef));
cout << n++ << "\t\t" << xn << "\t\t" << Function(B, xn) << endl;
x0 = x1;
x1 = xn;
if (n > 3000)
{
cout << "迭代失败" << endl;
return 0;
}
}
return xn;
}

3.4数据结构部分
l 数据结构头文件
#ifndef _SQUENCELIST_H
#define _SQUENCELIST_H

#include "stdio.h"
#include "stdlib.h"
#include "stdafx.h"
#include<iostream>
using namespace std;

#define maxsize 1024

/**
*sequenlist
*/
typedef int datatype;
typedef struct
{
datatype data[maxsize];
int last;
}sequenlist;
sequenlist *InitList();
int Length(sequenlist*);
int Insert(sequenlist*, datatype, int);
int Delete(sequenlist*, int);
int Locate(sequenlist*, datatype);
void del_node(sequenlist*, datatype);
void PrintList(sequenlist*);
int Compare_L(sequenlist*, sequenlist*);
void Invert(sequenlist*);

/**
*linklist
*/
typedef char linkdatatype;
typedef struct node
{
linkdatatype data;
struct node*next;
}linklist;
linklist* CreateListF();
#endif

l 数据结构CPP文件
#include "stdafx.h"
#include "squencelist.h"
///////////////////////////////////数据结构部分///////////////////////////////////////////
///////////////////////////////////sequenlist///////////////////////////////////////////
sequenlist *InitList()
{
sequenlist*L = (sequenlist*)malloc(sizeof(sequenlist));
L->last = 0;
return L;
// sequenlist*L = new sequenlist;
}

int Length(sequenlist*L)
{
return L->last;
}

int Insert(sequenlist*L, datatype x, int i)
{
int j;
if (L->last >= maxsize - 1)
{
cout << "表已满" << endl;
return 0;

}

for (j = L->last; j >= i; j--)
L->data[j + 1] = L->data[j];
L->data[i] = x;
L->last++;
return 1;
}

int Delete(sequenlist*L, int i)
{
int j;
if ((i<1) || (i>L->last))
{
cout << "非法删除位置" << endl;
return 0;
}
for (j = i; j <= L->last; j++)
L->data[j] = L->data[j + 1];
L->last--;
return 1;
}

int Locate(sequenlist*L, datatype x)
{
int i = 1;
while (i <= L->last)
{
if (L->data[i] != x)i++;
else return i;
}
return 0;
}

/*顺序表中删除所有元素为x的结点*/
void del_node(sequenlist*L, datatype x)
{
int i = Locate(L, x);
while (i != 0)
{
if (!Delete(L, i))break;
i = Locate(L, x);
}
}

void PrintList(sequenlist*L)
{
int i = 1;
for (i = 1; i <= L->last; i++)
cout << L->data[i] << ' ';
cout << endl;

}

int Compare_L(sequenlist*A, sequenlist*B)
{
int j = 1;
int i = 0;
int n, m;
n = A->last;
m = B->last;
while ((j <= n) && (j <= m))
{
if (A->data[j] == B->data[j])i = 0;
if (A->data[j] < B->data[j])
{
i = -1;
break;
}
if (A->data[j] > B->data[j])
{
i = 1;
break;
}
j++;
}
if (i != 0)return i;
else
{
if (m < n)i = 1;
if (n < m)i = -1;
if (m == n)i = 0;
return i;
}
}

void Invert(sequenlist*L)
{
int i;
int temp;
for (i = 1; i <= L->last / 2; i++)
{
temp = L->data[i];
L->data[i] = L->data[L->last + 1 - i];
L->data[L->last + 1 - i] = temp;

}
}

///////////////////////////////////linklist///////////////////////////////////////////
linklist* CreateListF()
{
linklist *head, *p;
char ch;
head = (linklist*)malloc(sizeof(linklist));
head->next = NULL;
cin >> ch;
while (ch != '\n')
{
p = (linklist*)malloc(sizeof(linklist));
p->data = ch;
p->next = head->next;
head->next = p;
}
return head;
}

4运行结果
4.1二分法运行结果

4.2牛顿迭代法运行结果

4.3割线法运行结果

边界情况调试
l 二分法方程的根导数也为零的情况

l 牛顿迭代法导数为零的情况

5总结
这次的程序设计题看似简单实则临界代码区很多，调试时很容易出错。
C++的输入输出数据流对于不定数字的输入显得很麻烦，在输入方程系数的时候对于任意阶数的方程由于C++没有动态扩展内存的功能几乎不能交互，设定一个很大的宏显然浪费空间。于是想先确定最高阶数并保存在变量中，系数的读取则使用循环，由于C++读取数据的特点还能防止输入的系数个数和需要的个数不相符，使用00作为结束标志不会和0冲突。
因为方程的阶数是不定的，所以考虑顺序表的存储方式。

6参考资料
《计算方法与实习》孙志忠等著 第五版---东南大学出版社
《软件技术基础》周大为等著 第一版---西安电子科技大学出版社