对角排序数组 [英] Sorting an array diagonally
问题描述
我查过一些网站，但找不到我的问题的答案。
这是我的代码：
#includestdafx.h
#include< iostream>
#include< math.h>
#include< time.h>
＃include< iomanip>
＃include< array>
#include< algorithm>
using namespace std;
const int AS = 6;
int filling（void）;
void printing（int [AS] [AS]）;
int forsorting（int [] [AS]，int）;
int main（）
{
int funny = 0;
int timpa = 0;
int counter = 0;
int Array [AS] [AS];
srand（time（0））;
for（int i = 0; i
for（int j = 0; j
}
cout<< 未排序的数组是< endl<< endl;
printing（Array）;
cout<< 排序的数组是< endl<< endl;
for（int il = 0; il
for（int elle = 0; elle< AS; elle ++ ）
Array [il] [elle] = forsorting（Array，funny）;
printing（Array）;
}
系统（PAUSE）;
return 0;
}
int fill（void）
{
int kira;
kira = rand（）％87 + 12;
return kira;
}
void print（int Array [AS] [AS]）
{
int counter = 0;
for（int i = 0; i
for（int j = 0; j
cout ;& setw（5）<< Array [i] [j];
计数器++;
if（counter％AS == 0）
cout<< endl<< endl;
}
}
}
int forsorting（int Array [AS] [AS]，int funny）
{
int c， tmp，x;
int dice = 0;
int Brray [AS * AS];
int timpa = 0;
int super = 0;
//转换数组[] []到Brray []
for（int i = 0; i
for（int k = 0; k
Brray [timpa] = Array [i] [k]
timpa ++;
}
}
// Brray中的冒泡排序[]
for（int passer = 1; passer< = AS -1; passer ++）
{
for（int timon = 1; timon <= AS-1; timon ++）
{
if（Brray [timpa] timpa + 1]）$ b $ b {
super = Brray [timpa];
Brray [timpa] = Brray [timpa + 1];
Brray [timpa + 1] = super;
}
}
}
//将ArrayArray []转换为Array [] []
for（int e = 0; e
for（int d = 0; d
Brray [dice] = Array [e] [d]
dice ++;
}
}
***这里有一个缺失的部分***
}
我需要做的是，使用3个函数编写程序。
- 第一个函数会随机填充我的2D数组（这部分没有问题）
- 第二个函数将在屏幕上打印未排序的数组（此部分没有问题）
- ，第三个函数将对角排列数组，如下图所示：
然后我需要调用第二个函数打印排序的数组。我的问题是与第三个函数我把我的2D数组变成一个1D数组，并使用气泡排序排序，但我不能做的是把它变回一个二维数组对角排序。
<假设你有一个基于0的一维数组
A of n = m ^ 2 元素。我将告诉你如何根据你的对角化方法得到一个索引到 A ，给定和一对索引到一个二维数组。我将在 A 中调用 i （从0开始）索引，并且 x 和 y 二维数组中的（基于0）索引。 首先，让我们假设我们知道 x 和 y 。对角线中包含（x，y）的所有条目的坐标总和相同。让 sum = x + y 。在你到达包含这个条目的对角线之前，你通过 sum 更早的对角线迭代（检查这是正确的，由于基于零的索引）。总和 k 的对角线总共具有 k + 1 条目。所以，在得到这个对角线之前，你迭代了 1 + 2 + ... +（sum - 1）条目。存在用于形式 1 + 2 + ... + N ，即 N *（N + 1）/ 2 。所以，在到达这个对角线之前，你通过（sum-1）* sum / 2 条目迭代。
现在，在进入（x，y）之前，你在这个对角线中经过了几个条目，不是吗？多少？为什么，它是 y ！你从顶部入口开始，一次下去一个。因此，（x，y）的条目是（（sum-1）* sum / 2 + y + 1） th条目，但是数组也是基于零的，所以我们需要减去一个。所以，我们得到公式：
-
i =（sum - 1）* sum / 2 + y = x + y-1）*（x + y）/ 2 + y
要回退，我们要从 i 开始，并找出（x，y）对在元素 A [i] 的二维数组。因为我们正在解决从一个开始的两个变量（ x 和）和一个约束，写下一个闭合的公式是棘手的。事实上，我不相信封闭的形式是可能的，当然不是没有一些 y 地板等，我开始试图找到一个，放弃了！祝你好运！
这是正确和更容易生成（x，y） i ，请记住坐标对的总和在您的一个对角线内是常数。
I've looked up some websites but I couldn't find an answer to my problem.
Here's my code:
#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <time.h>
#include<iomanip>
#include<array>
#include <algorithm>
using namespace std;
const int AS = 6;
int filling(void);
void printing(int[AS][AS]);
int forsorting(int[][AS], int);
int main()
{
int funny = 0;
int timpa = 0;
int counter = 0;
int Array[AS][AS];
srand(time(0));
for (int i = 0; i<AS; i++)
{
for (int j = 0; j<AS; j++)
Array[i][j] = filling();
}
cout << "The unsorted array is" << endl << endl;
printing(Array);
cout << "The sorted array is" << endl << endl;
for (int il = 0; il<AS; il++)
{
for (int elle = 0; elle<AS; elle++)
Array[il][elle] =forsorting(Array, funny);
printing(Array);
}
system("PAUSE");
return 0;
}
int filling(void)
{
int kira;
kira = rand() % 87 + 12;
return kira;
}
void printing(int Array[AS][AS])
{
int counter = 0;
for (int i = 0; i<AS; i++)
{
for (int j = 0; j<AS; j++)
{
cout << setw(5) << Array[i][j];
counter++;
if (counter%AS == 0)
cout << endl << endl;
}
}
}
int forsorting(int Array[AS][AS], int funny)
{
int c, tmp, x;
int dice = 0;
int Brray[AS*AS];
int timpa = 0;
int super = 0;
//Transofrming Array[][] into Brray[]
for (int i = 0; i < AS; i++)
{
for (int k = 0; k < AS; k++)
{
Brray[timpa] = Array[i][k];
timpa++;
}
}
//Bubble sorting in Brray[]
for (int passer = 1; passer <= AS-1; passer++)
{
for (int timon = 1; timon <= AS-1; timon++)
{
if (Brray[timpa]>Brray[timpa + 1])
{
super = Brray[timpa];
Brray[timpa] = Brray[timpa + 1];
Brray[timpa + 1] = super;
}
}
}
//Transforming Brray[] into Array[][]
for (int e = 0; e<AS; e++)
{
for (int d = 0; d<AS; d++)
{
Brray[dice] = Array[e][d];
dice++;
}
}
***There's a part missing here***
}
What I have to do is, write a program using 3 functions.
- The 1st function would fill my 2D array randomly (no problem with this part)
- the 2nd function would print the unsorted array on the screen (no problem with this part)
- and the 3rd function would sort my array diagonally as shown in this picture:
Then I need to call the 2nd function to print the sorted array. My problem is with the 3rd function I turned my 2D array into a 1D array and sorted it using Bubble sorting, but what I can't do is turn it back into a 2D array diagonaly sorted.
Suppose you have a 0-based 1-dimensional array A of n = m^2 elements. I'm going to tell you how to get an index into A, given and a pair of indices into a 2D array, according to your diagonalization method. I'll call i the (0-based) index in A, and x and y the (0-based) indices in the 2D array.
First, let's suppose we know x and y. All of the entries in the diagonal containing (x,y) have the same sum of their coordinates. Let sum = x + y. Before you got to the diagonal containing this entry, you iterated through sum earlier diagonals (check that this is right, due to zero-based indexing). The diagonal having sum k has a total of k + 1 entries. So, before getting to this diagonal, you iterated through 1 + 2 + ... + (sum - 1) entries. There is a formula for a sum of the form 1 + 2 + ... + N, namely N * (N + 1) / 2. So, before getting to this diagonal, you iterated through (sum - 1) * sum / 2 entries.
Now, before getting to the entry at (x,y), you went through a few entries in this very diagonal, didn't you? How many? Why, it's exactly y! You start at the top entry and go down one at a time. So, the entry at (x,y) is the ((sum - 1) * sum / 2 + y + 1)th entry, but the array is zero-based too, so we need to subtract one. So, we get the formula:
i = (sum - 1) * sum / 2 + y = (x + y - 1) * (x + y) / 2 + y
To go backward, we want to start with i, and figure out the (x,y) pair in the 2D array where the element A[i] goes. Because we are solving for two variables (x and y) starting with one (just i) and a constraint, it is trickier to write down a closed formula. In fact I'm not convinced that a closed form is possible, and certainly not without some floors, etc. I began trying to find one and gave up! Good luck!
It's probably correct and easier to just generate the (x,y) pairs iteratively as you increment i, keeping in mind that the sums of coordinate pairs are constant within one of your diagonals.
这篇关于对角排序数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
