Stuck with a spiral triangle
I'm looking for an algorithm that prints and prints a triangle with sides n (or half a square), where n is the input to the program. But numbering starts at the top of the triangle, goes diagonally, back along the bottom row, and up the left edge. If there is interior space, it goes diagonally downward from the largest number and continues.
Here's an example:
1
9 2
8 10 3
7 6 5 4
Here is my code and it results in:
1
10 2
9 8 3
7 6 5 4
Is there any algorithm for this program if there is any explanation for me. The above program works well with a smaller line size 3
, but not for a higher size 3
.
#include<iostream.h>
#include<conio.h>
void main()
{
int n,i,j,v=0;
static int k;
clrscr();
cout<<"Enter the number of rows : ";
cin>>n;
for(i=0;i<n;i++)
{
for(j=0;j<=i;j++)
{
v++;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
cout<<v;
cout<<"\t";
v--;
}
while(k==i)
{
k++;
cout<<k;
cout<<"\t";
}
cout<<"\n";
}
getch();
}
source to share
Here is a solution that doesn't use array memory. A spiral can be thought of as a collection of right-angled triangles inside each other. The function iterates over all rows and columns and for each position, calculates which triangle contains the element by finding the closest distance to the edge of the outer triangle, then calculates the adjusted position (x, y) relative to the top position, the left corner of that inner triangle, the number of rows of the inner triangle (r) and the starting number of the inner triangle (start + 1). It then outputs a number based on whether it lies on the diagonal, horizontal, or vertical side.
#include <iostream>
#include <iomanip>
using namespace std;
int main(void) {
int rows;
cout << "Enter the number of rows : ";
cin >> rows;
int i, j;
for(i = 0; i < rows; i++)
{
for(j = 0; j <= i; j++)
{
// find the closest side:
int distance = j; // distance to vertical side
if(i-j < distance)
distance = i-j; // distance to diagonal side
if((rows-1)-i < distance)
distance = (rows-1)-i; // distance to horizontal side
int r = rows - distance * 3;
// compute position on inner triangle:
int x = j - distance;
int y = i - distance * 2;
// compute start number for inner triangle:
int start = (((rows+1)*rows)/2) - (((r+1)*r)/2);
// output number based on side:
if(x==y) // diagonal side
cout << setw(2) << (start+y+1) << " ";
else if(y==(r-1)) // horizontal side
cout << setw(2) << (start+(r*2)-(x+1)) << " ";
else // vertical side
cout << setw(2) << (start+(r*3)-(y+2)) << " ";
}
cout << endl;
}
return 0;
}
Take an example where the rows are 7. In this case, the value distance
for each item would be:
(0)
0 0
0 (1) 0
0 1 1 0
0 1 (2) 1 0
0 1 1 1 1 0
0 0 0 0 0 0 0
All elements with the same distance value form a triangle. The number of rows of the outer triangle is 7, and the next smaller one is 4, then 1. So r = rows - (distance * 3).
The upper left corner of the outer triangle is at row 0, column 0. The first inner triangle is at row 2, column 1, the next is at row 4, column 2. So the position of this row / position of the column on the inner triangle it lies on , is found by subtracting the distance * 2 from the row and the distance from the column, so y = i - (distance * 2) and x = j - distance.
The inner column of the triangle is stored at x. The inner row of the triangle is stored at y. In the example above, the values ββin parentheses are the upper left corners of each triangle where x = 0 and y = 0. For example, for the upper left corner of a triangle with distance = 1, i = 2 and j = 1, so x = 1 - 1 = 0 and y = 2 - (1 * 2) = 0.
The initial value is obtained by calculating the number of elements in the entire large triangle ((row + 1) * row) / 2 and then subtracting the number of elements remaining, which is the number of elements in the inner triangle.
For a triangle with n rows, the total number of elements is ((n + 1) * n) / 2, as shown below for rows = 5:
1 X 0 0 0 0 0
2 X X 0 0 0 0
3 X X X 0 0 0
4 X X X X 0 0
5 X X X X X 0
1 2 3 4 5 6
To count the number of X, we can see that it is half the number of elements in the rectangle (5 + 1) * 5, so half of 30 is 15.
If there are two triangles one inside the other, for example:
X
X X
X O X
X O O X
X X X X X
and we want to count the number of X, then we can calculate the size of the whole triangle using the above formula to get 15, and then calculate the size of the inner triangle which has 2 rows as ((2 + 1) * 2) / 2 = 3. and subtracting the smaller from the larger gives 15 - 3 = 12. So, if there are 12 X, then the first O must be 13. This is how we can calculate the number to output for the upper left corner of the inner triangle.
Once you've calculated all this, you only need to figure out which side of the inner triangle the element is on and print it.
source to share
Here is a general idea on how to solve this problem using recursion. There is probably a way to solve this in a cost effective way, but I leave that for someone else. So let's say we store this as an array of arrays to be accessed x[i][j]
and let the size of the sides of the triangle be n. You can use google to create array of arrays dynamically.
Now what we want is the equation for the outside of the triangle. The numbers on the diagonal are (i (i + 1)) / 2 for 1 <= i <= n. The numbers along the left edge are 1+ (i (i-1)) / 2 for 1 <= i <= n. And the numbers along the bottom are 1+ (n (n-1)) / 2 .. (n (n + 1)) / 2.
So now to recursion. Let j be the size of the remaining triangle still numbered, k the largest number you encountered before, and (l, m) the index of the top of the triangle. Use the equations above and the previous information to calculate the number and store it in the remaining triangular array. If there is another interior, recursion with the highest numbered and vertex index. Etc.
Example of side size 4. First enter the number. The highest previous number is 0. The index of the first position is (0,0)
1
9 2
8 x 3
7 6 5 4
We're not done because we still have a size one interior. So when you recurse, the apex position of the triangle is (2,2), the largest number so far is 9, and the size of the remaining triangle is 1.
Now try side size 5. After the first numbering, we get:
1
12 2
11 x 3
10 x x 4
9 8 7 6 5
And the remaining triangle also starts at (2,2) as it did for side 4. But the size of the remaining triangle is now 2, and the largest number seen so far is 12.
After the recursion is complete, print the table.
source to share
The easy way is to use an array.
#include <iostream>
using namespace std;
int main(){
int n;
cout <<"Enter the number of rows : ";
cin >> n;
int **tri = new int *[n];
for(int i=0; i<n; i++){
tri[i] = new int[i+1];
}
int v = 0, r = 0, c = 0;
for(int k = n-1; 0 <= k; k -=3){//k is total side size / 3, next k -2 -1
if(k==0){
tri[r][c] = ++v;
break;
}
for(int i = 0; i < k; ++i)//β
tri[r++][c++] = ++v;
for(int i = 0; i < k; ++i)//β
tri[r][c--] = ++v;
for(int i = 0; i < k; ++i)//β
tri[r--][c] = ++v;
r += 2; ++c;//next start position
}
//print
for(r = 0; r < n; ++r){
for(c = 0; c <= r; ++c)
cout << tri[r][c] << '\t';
cout << endl;
}
for(int i=0; i<n; i++){
delete[] tri[i];
}
delete[] tri;
}
source to share