三角形问题_三角形问题的等价类表 - CSDN
精华内容
参与话题
  • 很不容易找到的资源,希望与大家一起分享。三角形问题是软件测试初学者应该熟悉的经典问题,本人一直苦于测试用例的编写,幸好找到这么好的东东,急于与大家分享。
  • 符号三角形问题

    千次阅读 2014-11-14 13:03:24
    下图所示的三角形中,有14个“+“和14个“-”。2个同号下面是+,两个异号下面是-。 + + - + - + + ...符号三角形问题,要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”相同。
         下图所示的三角形中,有14个“+“和14个“-”。2个同号下面是+,两个异号下面是-。

    + + - + - + +
    + - - - - +
    - + + + -
    - + + -
    - + -
    - -
    +

        在一般情况下,符号三角形的第一行有n个符号。符号三角形问题,要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”相同。

    利用回溯法,参考代码如下:
    #include <stdio.h>
    int sum,count;
    int half;
    int **p;
    int n;
    
    void backtrack(int t)
    {
    	int i,j;
    	if((count>half)||(t*(t-1)/2-count>half))
    		return;
    	if(t>n) sum++;
    	else
    	{
    		for(i=0;i<2;i++)
    		{
    			p[1][t]=i;
    			count=count+i;
    			for(j=2;j<=t;j++)
    			{
    				p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
    				count+=p[j][t-j+1];
    			}
    			backtrack(t+1);
    			for(j=2;j<=t;j++)
    				count+=p[j][t-j+1];
    			
    			count-=i;
    		}
    	}
    }
    
    
    int main()
    {
    
    	int i,j;	
    	printf("input the number of symbols in the first line:");
    	scanf("%d",&n);
    	
    	count=0; sum=0;
    	half=(n+1)*n/2;
    
    	if(half%2==1)
    	{
    		printf("the number is 0");
    		return 0;
    	}
    	
    	p=new int *[n+1];
    
    	for(i=0;i<n+1;i++)
    		p[i]=new int[n+1];
    
    	for(i=0;i<n+1;i++)
    		for(j=0;j<n+1;j++)
    			p[i][j]=0;
    
    	backtrack(1);
    
    	printf("the result is %d.\n",sum);
    	
    	return 0;
    }

    带输出结果的:
    #include <stdio.h>
    #include <math.h>
    
    int n,count=0,half,sum=0;
    int **a;
    
    
    void backtrack(int t)
    {
    	if(count>half || (t*(t+1)/2-count>half)) return;
    	int i,j;
    	if(t==n){	
    		sum++;
    		for(i=0;i<n;i++)
    		{
    			for(j=0;j<n-i;j++)
    			{
    				if(a[i][j])	
    					printf("-");
    				else
    					printf("+");
    			}
    			printf("\n");
    		}
    		printf("=====================\n");
    	}
    	else{
    		for(i=0;i<2;i++){
    			a[0][t]=i;
    			count=count+i;
    
    			for(j=1;j<=t;j++){
    				a[j][t-j]=a[j-1][t-j]^a[j-1][t-j+1];
    				count+=a[j][t-j];
    			}
    
    			backtrack(t+1);
    
    			for(j=1;j<=t;j++){				
    				count-=a[j][t-j];
    			}
    			count=count-i;
    		}
    	}
    }
    
    
    int main()
    {
    	int i,j,k;
    	scanf("%d",&n);
    	if((n*(n+1)/2)%2==1)
    	{
    		printf("result is 0.\n");
    		return 0;
    	}
    
    	half=n*(n+1)/4;
    	a=new int*[n];
    
    	for(i=0;i<n;i++)
    		a[i]=new int [n];
    
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<n;j++)
    			a[i][j]=0;
    	}
    
    	backtrack(0);
    
    	printf("the result is %d.\n",sum);
    
    	return 0;
    }








    展开全文
  • 三角形问题java代码

    2020-07-26 23:31:04
    三角形问题:输入三条边是否组成三角行并判断是什么样的三角形。
  • 三角形问题(3)

    2016-04-07 08:27:31
    问题及描述: /* *copyright(c) 2014,烟台... *All rights reserved *文件名称:test.cpp *作者:杨昊 ... *问题描述:三角形问题 *输入描述:无 *程序输出: */ #include using namespace std; cl

    问题及描述:

    /*
     *copyright(c) 2014,烟台大学计算机学院
     *All rights reserved
     *文件名称:test.cpp
     *作者:杨昊
     *版本:v6.0
     *时间;2016年4月7日
    
     *
     *问题描述:三角形问题
    
     *输入描述:无
     *程序输出:
    */
    
    #include<iostream>
    using namespace std;
    class Triangle
    {
    public:
     Triangle(int xx,int yy,int zz)
     {
      x=xx;
      y=yy;
      z=zz;
     }
     void showMessage()
     {
      cout<<x<<" "<<y<<" "<<z<<endl;
     }
    private:
     int x,y,z;
    };
    
    int main()
    {
     Triangle Tri(7,8,9);
     Tri.showMessage();
    }
    

    结果及总结:


    展开全文
  • 数学三角形问题

    2020-04-09 15:19:04
    问题描述:给定由一个n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和的最大值。 C语言代码如下: #include<stdio.h> #include<stdlib.h> #define MAXSIZE 10 int MaxTriangle(int v...

    问题描述:给定由一个n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和的最大值。
    C语言代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 10
    int MaxTriangle(int v[MAXSIZE][MAXSIZE],int n)
    {
    	int submax[MAXSIZE][MAXSIZE]={0};
    	for(int i=1;i<=n;i++)
    	{
    		submax[n][i]=v[n][i];
    	}
    	for(int k=n-1;k>=1;--k)
    	{
    		for(int r=1;r<=k;++r)
    		{
    			submax[k][r]=v[k][r]+(submax[k+1][r]>submax[k+1][r+1]?submax[k+1][r]:submax[k+1][r+1]);
    		}
    	}
    	return submax[1][1];
    }
    int main()
    {
    	int n;
    	int v[MAXSIZE][MAXSIZE];
    	printf("请输入三角形的行数:");
    	scanf("%d",&n);
    	printf("请输入三角形序列:\n");
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    			scanf("%d",&v[i][j]);
    	}
    	printf("%d",MaxTriangle(v,n));
    }
    
    

    在这里插入图片描述

    展开全文
  • 参加过大公司面试的读者都清楚,很多公司很喜欢出个算法题,然后评判候选人水平如何,笔者也有过类似经历,接下来是笔者总结的一些常见关于三角形类的算法题。 求面积 理论:除了常见公式S=1/2ah,还有一个不常见的...

    参加过大公司面试的读者都清楚,很多公司很喜欢出个算法题,然后评判候选人水平如何,笔者也有过类似经历,接下来是笔者总结的一些常见关于三角形类的算法题。

    1. 求面积
      理论:除了常见公式S=1/2ah,还有一个不常见的公式海伦公式,S=sqrt(s*(s-a)(s-b)(s-c))
      在这里插入图片描述
    2. 判断某个点是否在三角形内部
      理论:如果一个点在三角形内,其与三角形的三个点构成的三个子三角形的面积等于大三角形的面积。否则,大于大三角形的面积。
      在这里插入图片描述
      在这里插入图片描述

    参考文献
    1.百度百科之海伦公式
    2.Algorithm: 如何判断一个点是否在一个三角形内
    3.Github项目源代码

    展开全文
  • 动态规划-数字三角形问题

    千次阅读 2018-11-04 19:24:53
    有一个由非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数.  1  3 2  4 10 1 4 3 2 20 从第一行的数开始,每次可以往左下或右下走一格,直到走到最下行,把沿途...
  • 三角形问题

    2019-01-25 10:16:26
  • Problem B:数字三角形问题 Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形 的顶至底的一条路径,使该路径经过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 ...
  • 3-7 数字三角形问题 问题描述 给定一个由n行数字组成的数字三角形,如下图所示: 试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大(每一步只能从一个数走到下一层上和它最近...
  •  符号三角形第一行有n个符号,符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。   解题思路:  1、不断改变第一行的每个符号,搜索符合条件的解,可以使用...
  • 三角形问题的复杂之处在于输入与输出之间的关系比较复杂。) 分析题目中给出和隐含的对输入条件的要求: (1)整数 (2)三个数 (3)非零数 (4)正数 (5)两边之和大于第三边 (6)等腰 (7)等边 如果 a、 b ...
  • 三角形问题测试用例

    千次阅读 2019-05-19 21:18:15
    三角形问题测试用例
  • 符号三角形问题(回溯)

    千次阅读 2013-03-02 10:03:28
    /*回溯法解符号三角形问题    问题描述:  如下图是由14个“+”和14个“-”组成的符号三角形, 2个同号下面都是“+”,2个异号下面都是“-”。  - + + - + + +   - + - - + +   - - + -...
  • 软件测试--三角形问题源代码
  • 数字三角形问题 1.题目描述:给定一个由n行数字组成的数字三角形,如图3-7所示。设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。算法设计:对于给定的由n行数字组成的数字三角形,...
  • 该软件以研究三角形问题为目的. 通过用户选择三角形判断依据后,输入三角形的三条边长,通过相对应的功能判断出该三角形的类型. 当用户完成本次操作后,会提示是否继续操作.若退出操作即结束该程序. 二. 软件开发...
  • 符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的"+"和"-"的个数相同。 在一般情况下,符号三角形的第一行有n个符号。如图所示是由14个"+"号和14个"-"号组成的符号三角形。两个同号下面都...
  • 符号三角形问题 下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”,2个异号下面都是“-”。 在一般情况下,符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n,...
  • 数字三角形问题 时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte 总提交 : 213 测试通过 : 138  比赛描述 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出...
1 2 3 4 5 ... 20
收藏数 73,705
精华内容 29,482
关键字:

三角形问题