首页 > 基础算法 > 字符串处理 > hdu 1624 The Errant Physicist -计算几何-[解题报告]
2013
12-16

hdu 1624 The Errant Physicist -计算几何-[解题报告]

The Errant Physicist

问题描述 :

The well-known physicist Alfred E Neuman is working on problems that involve multiplying polynomials of x and y. For example, he may need to calculate

getting the answer

Unfortunately, such problems are so trivial that the great man’s mind keeps drifting off the job, and he gets the wrong answers. As a consequence, several nuclear warheads that he has designed have detonated prematurely, wiping out five major cities and a couple of rain forests.

You are to write a program to perform such multiplications and save the world.

输入:

The file of input data will contain pairs of lines, with each line containing no more than 80 characters. The final line of the input file contains a # as its first character. Each input line contains a polynomial written without spaces and without any explicit exponentiation operator. Exponents are positive non-zero unsigned integers. Coefficients are also integers, but may be negative. Both exponents and coefficients are less than or equal to 100 in magnitude. Each term contains at most one factor in x and one in y.

输出:

Your program must multiply each pair of polynomials in the input, and print each product on a pair of lines, the first line containing all the exponents, suitably positioned with respect to the rest of the information, which is in the line below.

The following rules control the output format:

  1.Terms in the output line must be sorted in decreasing order of powers of x and, for a given power of x, in increasing order of powers of y.
  2.Like terms must be combined into a single term. For example, 40x2y3 – 38x2y3 is replaced by 2x2y3.
  3.Terms with a zero coefficient must not be displayed.
  4.Coefficients of 1 are omitted, except for the case of a constant term of 1.
  5.Exponents of 1 are omitted.
  6.Factors of x0 and y0 are omitted.
  7.Binary pluses and minuses (that is the pluses and minuses connecting terms in the output) have a single blank column both before and after.
  8.If the coefficient of the first term is negative, it is preceded by a unary minus in the first column, with no intervening blank column. Otherwise, the coefficient itself begins in the first output column.
  9.The output can be assumed to fit into a single line of at most 80 charactes in length.
  10.There should be no blank lines printed between each pair of output lines.
  11.The pair of lines that contain a product should be the same length–trailing blanks should appear after the last non-blank character of the shorter line to achieve this.

样例输入:

-yx8+9x3-1+y
x5y+1+x3
1
1
#

样例输出:

  13 2    11      8      6    5     5 2     3    3
-x  y  - x  y + 8x y + 9x  - x y + x y  + 8x  + x y - 1 + y 

1

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;
//表示多项式中各项的结构体
struct TERM {
	//成员分别为系数,x指数和y指数
	int cof; int xe; int ye;
	//构造函数,按参数初始化变量
	TERM (int c, int x, int y) : cof(c), xe(x), ye(y) {}
};
//比较两项指数的大小,用于排序和合并同类项
bool GreaterTerm(const TERM &t1, const TERM &t2) {
	return (t1.xe > t2.xe || (t1.xe == t2.xe && t1.ye < t2.ye));
}
//解析输入多项式字符串的函数
void ParsePolynomial(char *pStr, vector<TERM> &Terms) {
	//循环处理每一项
	for (int nNum; *pStr != 0;) {
		//确定该项的正负号,并初始化项结构体
		TERM Term(*pStr == '-' ? -1 : 1, 0, 0);
		//如果前面有符号,则指针向后移位
		pStr += (*pStr == '-' || *pStr == '+') ? 1 : 0;
		//如果系数为0,则跳过整项
		if (*pStr == '0') {
			for(++pStr; *pStr != '\0' && *pStr != '+' && *pStr != '-'; ++pStr);
			continue;
		}
		//读取符号后面的系数
		for (nNum = 0; isdigit(*pStr); nNum = nNum * 10 + *pStr++ - '0');
		//如果系数不为0,则乘到项结构体的系数中去(保留原符号)
		for (Term.cof *= (nNum == 0) ? 1 : nNum; isalpha(*pStr);) {
			//循环读取两个变量的指针(如果存在),先确定是x还是y的指数
			int *pe = (*pStr == 'x') ? &Term.xe : &Term.ye;
			//读取后面的指数
			for (; isdigit(*++pStr); *pe = *pe * 10 + *pStr - '0');
			//没有指数即指数为1
			*pe = (*pe == 0) ? 1 : *pe;
		}
		//将新项结构体加入数组
		Terms.push_back(Term);
	}
}
//主函数
int main(void) {
	//循环读入所有输入的数据,遇到#号结束
	for (string str1, str2; cin >> str1 && str1 != "#"; ) {
		cin >> str2;
		if (str1.empty() || str2.empty()) continue;
		const int nMaxLen = 100;
		char szBuf1[nMaxLen], szBuf2[nMaxLen];
		vector<TERM> Poly1, Poly2, Result;
		//转存两个字符串以备解析多项式
		strcpy(szBuf1, str1.c_str());
		strcpy(szBuf2, str2.c_str());
		//解析两个多项式字符串
		ParsePolynomial(szBuf1, Poly1);
		ParsePolynomial(szBuf2, Poly2);
		vector<TERM>::iterator i, j;
		//执行多项式乘法
		for (i = Poly1.begin(); i != Poly1.end(); ++i) {
			for (j = Poly2.begin(); j != Poly2.end(); ++j) {
				TERM Term(i->cof * j->cof, i->xe + j->xe, i->ye + j->ye);
				Result.push_back(Term);
			}
		}
		//按项指数排序
		sort(Result.begin(), Result.end(), GreaterTerm);
		fill(&szBuf1[0], &szBuf1[nMaxLen], ' ');
		fill(&szBuf2[0], &szBuf2[nMaxLen], ' ');
		int nPos = 0;
		//查找同类项
		for (i = Result.begin(); i != Result.end(); ++i) {
			//合并后面的同类项(如果存在)
			for (j = i + 1; j < Result.end() &&
				i->xe == j->xe && i->ye == j->ye;) {
				i->cof += j->cof;
				j = Result.erase(j);
			}
			//如果该项的系数不为0,则将其输出
			if (i->cof != 0) {
				if (nPos > 0) { //不是第一项,输出中间的运算符
					++nPos;	//输出运算符前面的空格
					szBuf2[nPos++] = i->cof > 0 ? '+' : '-';
					szBuf2[nPos++] = ' ';
				}
				else { //第一项,输出前面的符号(如果为负)
					szBuf2[0] = '-';
					nPos += (i->cof < 0);
				}
				//如果系数(绝对值)不为1或xy指数都为0,则输出系数
				i->cof = abs(i->cof);
				if (i->cof != 1 || (i->xe == 0 && i->ye == 0)) {
					nPos += sprintf(&szBuf2[nPos], "%d", i->cof);
					//给sprintf擦屁股
					szBuf2[nPos] = ' ';
				}
				//如果x指数不为0,则输出x
				if (i->xe > 0) {
					szBuf2[nPos++] = 'x';
					if (i->xe > 1) {
						nPos += sprintf(&szBuf1[nPos], "%d", i->xe);
						szBuf1[nPos] = ' ';
					}
				} //同上
				if (i->ye > 0) {
					szBuf2[nPos++] = 'y';
					if (i->ye > 1) {
						nPos += sprintf(&szBuf1[nPos], "%d", i->ye);
						szBuf1[nPos] = ' ';
					}
				}
			}
		}
		//如果没有输出任何项,则多项式乘积为0
		if (nPos == 0) {
			szBuf2[nPos++] = '0';
		}
		//为多项式乘积字符串划结束符并输出
		szBuf1[nPos] = szBuf2[nPos] = '\0';
		cout << szBuf1 << '\n' << szBuf2 << endl;
	}
	return 0;
}

解题转自:http://www.cnblogs.com/devymex/archive/2010/08/18/1801966.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……