flameking


私信TA

用户名:201914040128

访问量:105

签 名:

等  级
排  名 7339
经  验 601
参赛次数 0
文章发表 3
年  龄 19
在职情况 学生
学  校 HUAS
专  业 计科

  自我简介:

声明:这道题我开始也不会写,但看了别人的题解有了思路,过了一段时间自己再来写,发现自己可以理解了;


解题思路:

对这种题目我们往往无法直接看穿他的思路,像数学题中的找规律题型一样,重点是如何得到它的变化方程;

首先我们先定义以下几个变量

m:直线的总数

n:平行直线的数目

sum:交点个数;

这里我不做系统的规律分析,只讲一下我的思路:1.相互平行的直线有零个交点,不相互平行的直线之间一定有一个交点;我们假设有6条直线,其中2条平行,那么另外4条与这两条直线有2*4=8个交点,我们把这个部分定为part1,而4条互相不平行的直线有4*(4-1)/2=6个交点,我们把它称为part2,平行的两条直线之间交点数=0,我们定为part3(它总为零),显然从这里可以看出这是一个动态规划问题,那么重点就是状态转移方程:即sum = part1+part2(+part3 )= n*(m-n)(m-n)条直线的交点数 (+ 0)我们把它称为(一); 

注意事项:

但平行的直线数目n>=4时有不同的情况,需分别考虑;而这种特殊情况可以这样处理,即当m=4时,设平行线n=2,而另外两条线有两种情况:1,不平行,2,平行;而这不就是当n=2时所有可能交点的的情况吗?因而到这我们的状态转移方程应该改位:sum = part1 + part2(+part3) = n*(m-n) + (m-n)条直线交点的集合我们把它称为(二),由以上分析,(二)是包含(一)的,所以我们最终的状态转移方程就是(二)

参考代码:

SharedScreenshot.jpg

#include <iostream>
#include <cstdio>
#include <string.h>
#define limit_max 21
#define max_point 200

using namespace std;

int main()
{
    int M;      //直线的数目
    int r, c;   //行列下标
    int point[limit_max][max_point];
    memset(point, 0, sizeof(point));
    /**<
        行下标r代表直线数目,列下标c代表交点数目,
        而point[r][c]的值(0,1)则代表交点数是否存在
    */
    //first
    for(r=0; r<limit_max; r++)
        point[r][0] = 1;                    //对任意的r,当所有的直线互相平行时,c==0;
    for(r=2; r<limit_max; r++)
    {
        c = r*(r-1)/2;
        point[r][c] = 1;
    }
    //second
    int m, n;                               //直线数目m,平行直线数目n(n=1, 2, 3......m);
    for(m=2; m<limit_max; m++)
        for(n=m-1; n>=2; n--)               //交点数sum = n*(m-n) + (m-n)条直线的交点数;
        {
           int  n_part = m-n;
           for(c=0; c<=n_part*(n_part-1)/2; c++)
           {
               if(point[n_part][c] == 1)
                    point[m][n*n_part+c] = 1;
           }
        }

    while (~scanf("%d", &M))
    {
        for(c=0; c<=M*(M-1)/2; c++)         // M*(M-1)/2 表示最大下标数
        {
            if(point[M][c])
                cout << c << ' ';
        }
        cout << endl;
    }

    return 0;
}


 

0.0分

2 人评分

  评论区