先来看看题目:
描述
康托尔三角是由著名数学家康托尔设计的一个整数三角,可以用来证明所有有理数与自然数一一对应,亦即有理数集是一个可数集。康托尔三角的构造如下:
01 02 06 07 15 16 28 29 45 46
03 05 08 14 17 27 30 44 47
04 09 13 18 26 31 43 48
10 12 19 25 32 42 49
11 20 24 33 41 50
21 23 34 40 51
22 35 39 52
36 38 53
37 54
55
它的填充规律是:将自然数按照从小到大的顺序从左上角往右下角按照蛇形排列:从左下到右上,再从右上到左下,每当到达边界之后就改变填充方向。
按照这种方式填充的三角形,给定行值和列值之后,填充的自然数是确定的。
规定行值和列值均从1开始计算。用(行,列)的方式进行描述。那么有:
(1,1)为1,(1,4)为7,(3,4)为18,(6,5)为51,(8,2)为38.
给定一个行值r和列值c,请求出对应的自然数。题目保证1≤r,c≤10,000
格式
输入格式
一行,两个整数,中间用空格分隔,表示行值r和列值c。
输出格式
一个正整数,表示该位置应填充的数据
样例
输入样例
5 4
输出样例
33
首先我想到的是用数组将这个三角形打表,但是很可惜,超内存了!后面苦思冥想,发现了其中的规律。
现在假设轮替的轮数为 turn ,我们可以发现通过所给出的行值和列值得到所属的轮数。比如数字9(2,3),11(5,1)。turn=r+c-1.
知道轮数之后一切都好办了,这时候我们分turn为奇数和偶数考虑,利用等差数列求和公式来计算。
超内存代码:
public class Main{
Scanner s=new Scanner(System.in);
int r,c;
int[][] SnakeMatrix=new int[10000][];
int turn=1,cnt=1,i,j;
for(i=0;i<10000;i++) {
SnakeMatrix[i]=new int[10000-i];
}
while(turn<=10000) {//模拟生成蛇形矩阵
if(turn%2==1) {
for(i=turn-1,j=0;i>=0&&j<=turn-1;i--,j++) {
SnakeMatrix[i][j]=cnt++;
}
}else {
for(i=0,j=turn-1;i<=turn-1&&j>=0;i++,j--) {
SnakeMatrix[i][j]=cnt++;
}
}
turn++;
}
}
文章来源:https://www.toymoban.com/news/detail-716430.html
AC代码 文章来源地址https://www.toymoban.com/news/detail-716430.html
import java.util.Scanner;
public class SnakeMatrix {
public static void main(String[] args) {
Scanner get=new Scanner(System.in);
int r,c,turn,ans;
int n=10;
r=get.nextInt();
c=get.nextInt();
turn=r+c-1;
if(turn%2!=0){
ans=(turn+1)/2*turn-(turn-c);
}else{
ans=turn/2*(turn+1)-c+1;
}
System.out.println(ans);
}
}
到了这里,关于蛇形矩阵蒸滴好玩的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!