Z字形排列问题
字形编排过程大致是这样的：经过前期处理的图像被分为若干个 的小图像块，此时就从小图像块的左上角开始沿Z字形对图像元素进行遍历，并将遍历所得的结果重新写入等大小的图像块中
Z字形编排问题主要应用在JPEG编码上，也叫Zigzag。主要思路就是从左上角第一个像素开始以Z字形进行编排。
![]()
经过Z自行排列之后，原图像矩阵中的序号变为如下图所示：
![]()
总结规律
对于原始矩阵matrix中的任意元素matrix[i][j]的遍历走向规律可以分为如下三种情况（偶数情况下）
-
1、如果二维数组中的元素matrix[i][j]中纵坐标j是偶数，且i=0或者i=7，那么遍历路径在矩阵中的走向就是水平向右移动一格。
-
2、如果二维数组中的元素matrix[i][j]中横坐标i是奇数，且j=0或者j=7，，那么遍历路径在矩阵中的走向就是垂直向下移动一格。
-
3、除上述规则以外的情况，如果二维数组中的元素matrix[i][j]的横纵坐标和i+j是偶数，则遍历路径在矩阵中的走向就是右上角移动一格；否则，若i+j是奇数，则遍历路径在矩阵中的走向就是左下角移动一格。
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include<iostream>
#include<iomanip>
using namespace std;
#define SIZE 8
int main(int argc, char** argv){
int matrix[SIZE][SIZE]={0};
int a[SIZE][SIZE]={0};
int i,j ,x,y,value=0;
int *p;
p=&matrix[0][0];
for(i=0;i<SIZE*SIZE;i++){
*p++=i;
}
cout<<"原始矩阵如下:"<<endl;
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
cout<<setw(4)<<*(*(matrix+i)+j);
}
cout<<endl;
}
i=0;j=0;
for(x=0;x<SIZE;x++){
for(y=0;y<SIZE;y++){
*(*(a+i)+j)=*(*(matrix+x)+y);
if((i==SIZE-1||i==0)&&j%2==0){
j++;
continue;
}
if((j==0||j==SIZE-1)&&i%2==1){
i++;
continue;
}
if((i+j)%2==0){
i--;
j++;
}else if((i+j)%2==1){
i++;
j--;
}
}
}
cout<<endl<<"经过Z字形编排后的矩阵如下:"<<endl;
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
cout<<setw(4)<<*(*(a+i)+j);
}
cout<<endl;
}
}
|
大整数乘法问题
由于计算机精度有限，因此单纯使用程序设计语言提供的原子数据类型来完成两个大整数的乘法显然是不合时宜的。因此考虑采用数组对大整数的每一位进行保存再进行运算从而解决了大整数的运算问题。
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <iostream>
using namespace std;
#include <memory.h>
#define SIZE 14
int* multi(int* num1, int size1, int* num2, int size2)
{
int size = size1 + size2;
int *ret = new int[size];
int i = 0;
memset(ret, 0, sizeof(int)*size);
for(i = 0; i < size2; ++i)
{
int k = i;
for(int j = 0; j < size1; ++j)
{
ret[k++] += num2[i] * num1[j];
}
}
for(i = 0; i < size; ++i)
{
if(ret[i] >= 10)
{
ret[i+1] += ret[i]/10;
ret[i] %= 10;
}
}
return ret;
}
int main()
{
int num1[SIZE] = {1, 1, 1, 1, 1, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int num2[SIZE] = {5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1};
int* rej = multi(num1, SIZE, num2, SIZE);
for(int i = SIZE*2-1; i >= 0; i--)
{
cout<< rej[i];
}
delete[] rej;
return 0;
}
|
九宫格问题
九宫格是一种古老的数学游戏，它要求在3X3的矩阵中，填入1-9这9个数字，并且横向、纵向、斜向上的3个数字之和皆相等。类似问题在数学上被称为幻方。现将九宫格推广到5X5，7X7等幻方问题。根据求解口诀““一居上行正中央,依次斜填切莫忘;上出框时向下放,右出框时向左放;排重便在下格填,右上排重一个样”。所谓一居上行正中央说的是1在第一行的正中，依次 斜填切莫忘说的是一直向右上方填， 上出框时往下填是斜填到方框上面去了，就放在这竖行的最下边， 右出框时左边放是说斜填到右框外面，就在横行左边放， 排重便在下格填是斜填上面有数字了，就在自己的下面放， 右上排重一个样就是右上格上面没有格子了，就和排重一样，放在自己的下面。
根据一个用户输入的奇数，作为幻方矩阵的大小输出一个对应的矩阵。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include<iostream>
#include<iomanip>
#include<memory.h>
using namespace std;
int main(int argc,char** argv)
{
cout<<"请输入幻方的大小n:";
int n=1;
cin>>n;
cout<<endl;
int **a=new int*[n];
for(int i=0;i<n;++i){
a[i]=new int[n];
memset(a[i],0,n*sizeof(int));
}
int row=0;
int col=n/2;
for(int i=1;i<=n*n;i++){
a[row][col]=i;
row--;
col++;
if(row<0&&col>=n){
col--;
row+=2;
}else if(row<0){
row=n-1;
}
else if(col>=n){
col=0;
}else if (a[row][col]!=0){
col--;
row+=2;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<setw(6)<<a[i][j];
}
cout<<endl;
}
for(int i=n;i>0;){
delete[] a[--i];
}
delete[] a;
return 0;
}
|
约瑟夫环问题
N个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈。（模拟此过程，输出出圈的人的序号）
链表解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
import java.util.LinkedList;
import java.util.Scanner;
public class Solution {
public static int Joseph(int n,int m){
LinkedList<Integer> queue=new LinkedList<>();
for(int i=1;i<=n;i++){
queue.add(i);
}
while(queue.size()!=1){
for(int i=1;i<m;i++){
queue.add(queue.poll());
}
int num=queue.poll();
System.out.println(num);
}
System.out.println("最后幸存的编码为:"+queue.peek());
return queue.peek();
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
sc.close();
Joseph(n,m);
}
}
|
数学解法:
1
2
3
4
5
6
7
|
public int LastRemaining_Solution(int n, int m) {
if (n == 0)
return -1;
if (n == 1)
return 0;
return (LastRemaining_Solution(n - 1, m) + m) % n;
}
|
魔术师发牌问题
魔术师利用一副牌中的13张黑桃牌，预先将他们排好后叠放在一起，牌面朝下。对观众说：“我不看牌，只数数就可以猜到每张牌是什么，
我大声数数，你们听，不信？现场演示。”魔术师将牌堆最上面的哪张排数为1，把他翻过来正好是黑桃A，将黑桃A从牌堆抽出放在桌子上，
第二次数1、2，将第一张放在牌堆最下面，第二张翻开，正好是黑桃2，也将它抽出放在桌子上。这样依次进行将13将牌全部翻出，准确无误。问牌最开始的顺序是怎样排的。
![]()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<iostream>
using namespace std;
int main(){
int a[13];
for(int i=1;i<13;i++){
a[i]=0;
}
a[0]=1;
int n=1;
for(int i=2;i<14;i++){
for(int j=0;j<i;){
if(a[n%13]==0){
j++;
if(j==i){
a[n%13]=i;
break;
}
}
n++;
}
}
for(int i=0;i<13;i++){
cout<<a[i]<<" ";
}
return 0;
}
|
拉丁方阵的问题
拉丁方阵是一种n×n的方阵，方阵中恰有n种不同的元素，每种元素恰有n个，
并且每种元素在一行和一列中恰好出现一次。著名数学家和物理学家欧拉使用拉
丁字母来作为拉丁方阵里元素的符号，拉丁方阵因此而得名。
![编程之美-22个经典问题]()
不知道你发现这样一个规律没？
比如3 x 3的拉丁方阵，第一行是1，2，3，第二行好像都向前移了一位，然后第一个元素跑到了最后面…
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include<iostream>
using namespace std;
int main(){
int n,i,j,k,t;
cout<<"please input num:";
cin>>n;
for(i=0;i<n;i++){/构造N个不同的拉丁方阵
for(j=0;j<n;j++){
t=(i+j)%n;
for(k=0;k<n;k++){
cout<<(k+t)%n+1;
}
cout<<endl;
}
cout<<endl;
}
return 0;
}
|
维吉尼亚加密法问题
https://www.cnblogs.com/inverseEntropy/p/10151176.html
括号匹配问题
FROM :blog.cfyqy.com | Author:cfyqy
评论