首页 > 编程学习 > 方程的解数 计蒜客 深度优先搜索

方程的解数 计蒜客 深度优先搜索

发布时间:2022/5/14 15:25:56

方程的解数 计蒜客 深度优先搜索

蒜头君在求解一个n元的高次方程:
在这里插入图片描述

其中:x1,x2,…,xn 是未知数,k1,k2,…,kn是系数,p1,p2,…,pn是指数。方程中所有数都一定是整数。
假设未知数 1≤xi≤M,i=1…n。你能帮蒜头君算出这个方程的整数解个数吗?

输入格式
第一行输入一个整数 n(1≤n≤4)。
第二行输入一个整数 M(1≤M≤150)。
第3行到第 n+2 行,每行输入两个整数,分别表示 ki(∣ki∣≤20)和 pi(1≤pi≤4)。两个整数之间用一个空格隔开。

输出格式
输出一行,输出一个整数,表示方程的整数解的个数。
样例输入
3
100
1 2
-1 2
1 2

样例输出
104

思路:深度优先搜索都可以化作寻路问题,本题的特点是每个位置的点的值可以重复,因此不需要visited标记位置是否访问过。由于dfs从n进入寻路,从x[1]这个位置开始,每个位置从1~M循环判断sum。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int k[30],p[10],x[10];
int n,M,count,sum=0;
double w,mypow[160][5];
void dfs(int a){
	if(a==0){//当1~n位置已经赋值 
		for(int i=1;i<=n;i++){//循环计算每一组k,x,p
			w=mypow[x[i]][p[i]];
			sum+=(int)w*k[i];
		}
		if(sum==0){
			count++;	
		}
		return ;//循环当前位置的下一个数 
	}
	for(int i=1;i<=M;i++){
		x[a]=i;//给当前位置赋值 
		sum=0;//计算前先将sum清零 
		dfs(a-1);
	}
}
int main(){
	scanf("%d",&n);
	scanf("%d",&M);
	for(int i=1;i<=n;i++){
		scanf("%d",&k[i]);
		scanf("%d",&p[i]);
	}
	for(double i=1;i<=150;i++){//此处用i<=M,内循环用i<=n会有测试数据不通过,?也许是因为测试数据在演我 
		for(double j=1;j<=4;j++){
			mypow[(int)i][(int)j]=pow(i,j);//数组下标必须为整型,并且double=pow[double,double] //用二维数组存储pow结果,如果在递归中用pow计算,会需要大量时间
		}
	}
	dfs(n);
	printf("%d",count);
	return 0;
}
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000