栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

平方拆分 , 数正方形,矩阵计数

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

平方拆分 , 数正方形,矩阵计数

平方拆分

【问题描述】 将 2019 拆分为若干个两两不同的完全平方数之和,一共有多少种不同的方 法?

        注意交换顺序视为同一种方法,例如 132 + 252 + 352 = 2019 与 132 + 352 + 252 = 2019 视为同一种方法。

答案:26287

(如果可以拆成0*0  那么答案:52574)

 

package The_tenth;


public class Three {
    static int sum;
    public static void main(String[] args) {
        //平方拆分
        dfs(2019,1,45);
        System.out.println(sum);
    }

        //深搜平方和为2019的所有子集
        private static void dfs(int num, int min, int max) {
            if (num < 0) {
                return;
            }
            if (num == 0) {
                sum ++;
                return;
            }
            //按顺序 2019- 1^2 - 2^2 ...-n^2
            //传入的第一个值为2019  第二个值为 组合2019的完全平方数 的其中一个
            //第二个值每轮+1  第一个值每轮都减去 第二个值的平方
            // 当num<0或者等于0时 (num:第一个值(2019))
            // 如果小于0那么return,然后回溯 继续 n的值+1 如果还是小于继续+1
            // 期间如果num=0了说明拼成了一次(即前面所有数的平方的和=2019)
            //n的值+到44后到达上限无法再加 然后再回溯改变n上一个数的值 ....
            //因为n是有序递增的 所以不会出现重复的顺序不同组成的值相同的情况
            for (int i = min; i < max; i++) {
                //去重,保证下一位数字一定大于当前数字
                dfs(num - i * i, i + 1, max);
            }
        }

}

数正方形

        【问题描述】 在一个 N × N 的点阵上,取其中 4 个点恰好组成一个正方形的 4 个顶点, 一共有多少种不同的取法?

         由于结果可能非常大,你只需要输出模 109 + 7 的余数。

        如上图所示的正方形都是合法的。

【输入格式】

        输入包含一个整数 N。

【输出格式】

         输出一个整数代表答案。

【样例输入】

        4

【样例输出】

        20

 

 

package The_tenth;

import java.util.Scanner;

public class G {
    public static void main(String[] args) {
        Scanner sn = new Scanner(System.in);
        int n = sn.nextInt()-1; //题目中的例子似乎是错的? 事实上3*3的点阵的正方形的数量才是20 如果要达到例子的效果 在接受输入值的时候-1即可(没明白什么意思)
        long count = 0;//正方形的数量
        long num = 1000000007;
        //平放
        // a 表示正方形边长
        //表面的正方形 边长从1 - 最大长度
        //count(正方形的总数量) +=  ( n(最大边长) - a(当前边长) + 1 ) *  ( n(最大边长) - a(当前边长) + 1 )
        //比如 当a = 1,n = 4的时候 count += (4-1+1) * (4-1+1) = 4 * 4 = 16 也就是边长为1的正方形 在4*4的表格中 有16个
        //再比如 当a = 2, n = 4的时候 count += (4-2+1)*(4-2+1) = 3*3 = 9  也就是边长为2的正方形 在4*4的表格中 有9个
        //原理就是 求出长度为4的表格 可以划出多少个 不同的长度为 2的表格
        for (int a = 1; a <= n; a++) {
            //a表示 当前正方形的边长 然后count += 当前边长正方行的数量
            count += (n - a+1) * (n - a+1);
//            System.out.println((n - a+1) * (n - a+1));
            count %= num;
        }
//        System.out.println(count);
        // 斜放
        //根据观察 1*1的矩阵 不存在正方形(指这个大小的矩阵特有的正方形)
        //2 * 2的矩阵 有一个斜边正方形 ;3 * 3的矩阵有 2个斜边正方形
        //观察发现 2*2的矩阵每个边有3个顶点 最左和最右的顶点无法构成斜边正方形
        //所以可以构成斜边正方形的顶点 就是 顶点数量 - 2(最左和最有的顶点)
        //每个顶点可以构成一个斜边正方行 所以 当前大小矩阵的特有斜边正方形数量 = 当前一个边顶点数-2
        for (int i = 1; i <= n; i++) {
            //i为当前矩阵长度
            // i+1 : 当前顶点数量
            // -2 : 因为最左和最右的顶点无法构成斜边正方形所以减去他们 就得到了当前顶点你数量 = 当前斜边正方形数量
            // (n-i+1) * (n-i+1) :表示当前最大矩阵 有多少个边长为i的正方形
            // count += 边长为i的矩形有的斜边正方形的数量  *  边长为N的矩形(最大边长)有多少个边长为i的矩形
            count += (i+1-2) * (n-i+1) * (n-i+1);
            count %= num;
        }
        System.out.println(count);

    }
}

矩阵计数

【问题描述】

        一个 N × M 的方格矩阵,每一个方格中包含一个字符 O 或者字符 X。

要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X。

问这样的矩阵一共有多少种?

【输入格式】

         输入一行包含两个整数 N 和 M。

【输出格式】

         输出一个整数代表答案。

【样例输入】

        2 3

【样例输出】

        49

【数据规模与约定】

对于所有评测用例,1 ≤ N, M ≤ 5。

 

package The_tenth;

import java.util.ArrayList;
import java.util.Scanner;

public class H {
    static int count = 0;
    static ArrayList> z = new ArrayList>();
    public static void main(String[] args) {
        //矩阵计数
        //每个格子有0(x),1(o)两种状态
        //假如矩阵有 a 列 那么每行都有2^m种情况(例如每行有3列 那么每行就有 2*2*2种情况)
        //加入有2列 每行有8种情况(8种是所有情况 实际应该筛掉行中不符合条件的情况 比如如果有3列 那么行一共有8种情况 但符合条件的有7种情况 所以我们使用的应该是7)
        // 那么一共就有8 *8种矩形 然后分别判断每个矩形是否符合条件就行了
        Scanner sr = new Scanner(System.in);
        int x = sr.nextInt();//行数
        int y = sr.nextInt();//列数
        int [][]jz = new int[x][y];
        int []xx = new int[y];
        ArrayList arr = new ArrayList();
        get(y,arr);//获取 每行的所有符合条件的可能性
        examine(0,jz);//将每行的情况组合起来并判断组合完后的矩形是否符合条件
        System.out.println(count);
//        for (ArrayList i: z){
//            System.out.println(i);
//        }
    }
    //获取所有符合条件的矩阵  i=当前行数
    public static void examine(int  i,int [][]jz){
        //当所有行都装完了(矩阵填充完毕)
        if (i>=jz.length){
            //判断当前填充结果是否符合条件
            if (getif(jz)){
                count++;
            }
            return;
        }

            //遍历行的所有符合条件可能
            for (int j = 0; j < z.size(); j++) {
                //设置当前行为当前可能性
                ArrayList zc = new ArrayList();
                zc = z.get(j);
                for (int k = 0; k < jz[i].length; k++) {
                    jz[i][k] = zc.get(k);
                }
                //当前行装完可能性后 装下一行
                examine(i+1,jz);
//                //清除当前行为空
//                for (int k = 0; k < jz[i].length; k++) {
//                    jz[i][k] = 0;
//                }
            }

    }
    //判断当前填充结果是否符合条件
    public static boolean getif(int [][]jz){
        //遍历
        for (int i = 0; i < jz.length; i++) {
            for (int j = 0; j < jz[i].length; j++) {
                //判断当前格子向右
                if (j+2 arr){
        if (arr.size()>=y){
            ArrayList temp = new ArrayList();
            temp.addAll(arr);
            //检查是否符合条件
            int sign = 0;
            for (int j = 0;j 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/943957.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号