30/09/2018, 16:39

Hỏi về 1 đoạn trong code mảng đệ quy: kiểm tra mảng tăng dần?

// kiểm tra mảng có tăng dân fhay không.cpp : Defines the entry point for the console application.
// kiểm tra xem mảng có thứ tự tăng hay không

#include "stdafx.h"
#include <iostream>
using namespace std;

#define MAX 100

// nhập mảng
void nhapmang(int a[], int n)
{
	if (n >=0 )
	{
		nhapmang(a, n - 1);
		cout << "phan tu thu a[" << n << "]" << ":";
		cin >> a[n];
	}
}
// in mảng
void inmang(int a[], int n)
{
	if (n >=0)
	{
		inmang(a, n - 1);
		cout << a[n] << "   ";
	}
}
// kiểm tra
int ktra(int a[], int n){
	//n là vị trí phần tử cuối cùng. Tức là khi truyền vào là n-1.
	// return 0 nếu dãy ko đổi. return 1 nếu dãy tăng
	if (n == 0) // Nếu chỉ có 1 phần tử tức là dãy ko đổi
		return 0;
	int t= ktra(a, n - 1);
	if ((a[n - 1] < a[n] && (t == 0 || t == 1)) || (a[n - 1] == a[n] && t == 1))
		return 1; 
	return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int a[MAX];
	int n;
	cout << "nhap n=";
	cin >> n;
	nhapmang(a, n - 1);
	inmang(a, n - 1);
	int k = ktra(a, n);
	if (k == 0)
		cout << "mang ko tang" << endl;
	else
		cout << "mang tang dan" << endl;
	return 0;
}

e thắc mắc gán int t= ktra(a, n - 1) để làm gì vậy mấy a

nhatlonggunz viết 18:40 ngày 30/09/2018

Cho em hỏi là code này đã chuẩn chưa, vì khi em nhập mảng kiểu gì nó cũng bào tăng dần

Ah, em đã sửa lại code của anh, chỗ này, vì trong hàm ktra, anh đặt n là vị trí phần tử cuối nên anh trong hàm main, anh phải đưa n - 1 vào (vì vị trí đầu tiên luôn là A[o])

int k = ktra(a, n);

thành

int k = ktra(a, n - 1);

Bây giờ nó chạy chuẩn rồi ấy

Còn về câu hỏi thì cái int t= ktra(a, n - 1); đó chính là đệ quy.

Để xét xem mảng có n phần tử (ở đây em vd n = 4 cho dễ hiểu) có tăng hay không, ta xét xem cũng trong chính mảng ấy mà chỉ có 3 phần tử, có tăng dần hay không.
Để xét xem 3 phần tử ấy có tăng dần không, ta tiếp tục xét xem 2 phần tử đầu có tăng dần hay không.
Tiếp tục như thế, ta xét 1 phần tử có tăng dần hay không, mà 1 phần tử thì được coi là luôn tăng dần (Trong đệ quy gọi đây là Base case).

Vì vậy, em nghĩ

if (n == 1) // Nếu chỉ có 1 phần tử tức là dãy ko đổi
		return 0;

phải chuyển thành

if (n == 1) // Nếu chỉ có 1 phần tử tức là dãy ko đổi
		return 1;

Có gì sai sót, anh @Gio giúp cái

Gió viết 18:54 ngày 30/09/2018

Sao không return lúc n=1 ấy. Lúc đó có cái nào khác để so sánh tăng giảm đâu. Post code hoàn chỉnh xem

nhatlonggunz viết 18:51 ngày 30/09/2018

Đã edit n == 1, sửa cái k mà với cái return mà quên mất n

Mà em giải thích đúng rồi phải không.
Với lại em cảm thấy đâu cần làm rắc rối thế nhỉ

X viết 18:46 ngày 30/09/2018

Chú này thích đệ quy

nhatlonggunz viết 18:44 ngày 30/09/2018

Mà nếu làm đệ quy thì làm thế này cũng được mà phải không

int ktra(int a[], int n){
	//n là vị trí phần tử cuối cùng. Tức là khi truyền vào là n-1.
	// return 0 nếu dãy ko đổi. return 1 nếu dãy tăng
	if (n == 1) // Nếu chỉ có 1 phần tử tức là dãy ko đổi
		return 0;
	if ((a[n - 1] < a[n])
		return 1; 
	return 0;
}

Gió viết 18:45 ngày 30/09/2018

Function Increase(a,n) = n<=1 or (a[n-1]>a[n-2] and increase(a,n-1));

int inc(int * a,int n){
     return n<=1 || ((a[n-1] > a[n-2]) && inc(a,n-1));
}

nhatlonggunz viết 18:52 ngày 30/09/2018

Là sao anh, em chả hiểu gì cả

X viết 18:54 ngày 30/09/2018

hàm này trông hư cấu quá nha @nhatlonggunz

nhatlonggunz viết 18:44 ngày 30/09/2018

Thế mà em test vẫn ngon :v

Gió viết 18:39 ngày 30/09/2018

Thế phần đệ quy đâu? Mà có n phần tử sao lại truy cập a[n] ?

nhatlonggunz viết 18:46 ngày 30/09/2018

Mà có n phần tử sao lại truy cập a[n]

Thì hàm main em gọi ktra(A, n - 1)

Thế phần đệ quy đâu?

Oops, đúng là hư cấu thật

return n<=1 || (a[n-1] > a[n-2]) && inc(a,n-1));

Hàm return ghê gớm đến mức độ này à, code này là gì thế ạ

kiencon viết 18:53 ngày 30/09/2018

code bạn gió dành cho người có kinh nghiệm, mình xin sửa lại code của bạn Long_Long

// 1. Hàm kiểm tra các phần tử của 1 mảng các số nguyên, trả về true nếu tăng dần, false nếu không thõa mãn
// Đầu vào: 1 mảng các số nguyên, tham trị số các số phần tử có trong mảng
// Đầu ra: true hoặc false
bool _laMangIntTangDan(int mang[], int soPhanTu){
	if (soPhanTu == 1) //mỏ neo
		return true;
	bool flag = _laMangIntTangDan(mang, soPhanTu - 1);
	if ((flag && mang[soPhanTu - 2] <= mang[soPhanTu - 1]))
		return true;
	return false;
}

mỏ neo (tức điều kiện để thoát đệ quy) là số phần tử của mảng chỉ có 1, nó luôn luôn đúng trả về true.
dùng biến tạm kiểu bool có tên flag để tiến hành đệ quy (quay lui để kiểm tra, ví dụ 4 phần tử, thì kiếm tra 3, 3 thì về 2, 2 thì về 1, 1 thì gặp cái mỏ neo trả về true, tức là lúc này biến flag của ta có giá trị true!
Lưu ý lúc này máy tính chưa biết giá trị trả về của hàm đối với 2, 3, 4 phần tử!
Nên ta có cái if phía sau để kiểm tra.
Đầu tiên flag có giá trị true, tức giá trị của hàm lúc mảng có 1 phần tử, máy đi vào hàm if để kiểm tra,
máy sẽ kiểm tra ngược lại lần lượt các mảng 2, 3, và 4 phần tử, tuy nhiên vì trong hàm chưa có điều kiện để kiểm tra hàm 2 hoặc nhiều hơn phần tử, nên ta lồng điều kiện kiểm tra bằng cách so sánh 2 phần tử cuối cùng trong mảng. máy sẽ kiểm tra ngược lại các mảng 2, 3 và 4 phần tử bằng cách này và gán giá trị true hoặc false cho biến flag.
Bằng cách này ta đã kiểm tra được lần lượt toàn bộ các phần tử trong mảng theo kiểu đệ quy.
PS: đó là cách hiểu của mình sau khi debug, các bạn nếu chưa hiểu thì có thể debug step by step bằng F11 trong visual để trực quan hơn.

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Long Long

0 chủ đề

0 bài viết

Tác giả nổi bật