C語言實現動態開闢儲存楊輝三角

2022-03-10 16:00:19

問題引入

楊輝三角相必大家並不陌生，第1行有1列、第二行有2列…第n行有n列，且每行行首和行尾的值都為1，其餘的值為上一行兩數相加

我們在C語言階段，第一次碰到的楊輝三角應該都是用常規的二維陣列儲存，可以觀察到，用綠色填充的空間都是沒有被利用的。

儲存1行浪費0個

儲存2行浪費1個

儲存3行浪費3個

儲存4行浪費6個

儲存n行浪費n*(n+1)/2-n個

解決方法

這樣極大浪費空間資源，今天我們就來試試動態開闢儲存楊輝三角，可以靈活的開闢空間，充分的利用空間。

思路分析

首先用指標pp維護動態開闢的int*型別的指標，再通過int*型別的指標去維護動態開闢的int型資料儲存楊輝三角

C程式碼實現

#include <stdio.h>
#include <stdlib.h>

void PrintFree(int** pp, int numrows)
{	
	//列印
	for (int i = 0; i < numrows; i++)
	{	
		for (int k = 0; k < numrows  -  i; k++)
		{
			printf("   ");
		}
		for (int j = 0; j <= i; j++)
		{
			printf("%4d", pp[i][j]);	//可以根據列印的行數適當調整右對齊
			printf("   ");
		}
		printf("n");
	}
}
	//清理malloc出來的空間
	for (int i = 0; i < numrows; i++)
	{
		free(pp[i]);
		pp[i] = NULL;
	}
}

int main()
{	
	//楊輝三角的行數
	int numrows;
	scanf("%d", &numrows);
	//開闢numrows個int*型別的指標用來維護int型的資料
	int** pp = (int**)malloc(sizeof(int*) * numrows);
	for (int i = 0; i < numrows; i++)
	{	
		//int型資料個數隨著行數的增加而增加
		pp[i] = (int*)malloc(sizeof(int) * (i + 1));
	}
	for (int i = 0; i < numrows; i++)
	{
		for (int j = 0; j <= i; j++)
		{	
			//每行的行首和行尾都是1
			if (j == 0 || i == j)
			{
				pp[i][j] = 1;     //	等價於 *(*(pp+i)+j)
			}
			//其餘的就是上一行的兩個資料相加
			else
			{
				pp[i][j] = pp[i - 1][j - 1] + pp[i - 1][j];
			}
		}
	}
	PrintFree(pp, numrows);

	return 0;
}

大家可以根據需要列印的行數大小在上面的列印函數適當調整

C++實現

用C++就非常方便了，STL中的vector就可以很方便的解決

#include <iostream>
#include <vector>
using namespace std;

//列印函數
void Print(vector<vector<int>> vv, int numrows)
{
	for (int i = 0; i < numrows; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			cout << vv[i][j] << "   ";
		}
		cout << endl;
	}
}
int main()
{	
	int numrows;
	cin >> numrows;
	vector<vector<int>> vv;
	for (int i = 0; i < numrows; i++)
	{	
		//每次開i+1個vector<int>
		vv.resize(i + 1);
		//每次開i+1個int
		vv[i].resize(i + 1);
	}
	for (int i = 0; i < numrows; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0 || i == j)
			{
				vv[i][j] = 1;
			}
			else
			{
				vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
			}
		}
	}
	Print(vv, numrows);

	return 0;

}

以上就是通過動態開闢的楊輝三角了

到此這篇關於C語言實現動態開闢儲存楊輝三角的文章就介紹到這了,更多相關C語言楊輝三角內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！