Đệ quy tìm Max, Min

lethanhbinh1997 · March 12, 2022, 11:44am

Anh chị nào hiểu cách tìm của chương trình tìm Max, Min không chỉ em với ạ, em xem mà không hiểu cách nó chạy ra sao để được giá trị Max, Min

int Min(int A[], int n)
{
	if (n == 0)
		return -1;
	if (n == 1)
		return A[0];
	else
	{
		if (A[n - 1] < Min(A, n - 1))
			return A[n - 1];
		else
			return Min(A, n - 1);
	}
}

int Max(int A[], int n)
{
	if (n == 0)
		return -1;
	if (n == 1)
		return A[0];
	else
	{
		if (A[n - 1] > Max(A, n - 1))
			return A[n - 1];
		else
			return Max(A, n - 1);
	}
}
void main()
{
	unsigned int n;
	int A[10] = { 4, 6, 3, 19, 22, 34, 67, 54, 15, 24 };
	printf("Gia Tri Nho Nhat Cua Mang: %d\n", Min(A, 10));
	printf("Gia Tri Lon Nhat Cua Mang: %d\n", Max(A, 10));
}

tcm · June 14, 2016, 2:40am

Cái này không nhất thiết phải dùng đệ quy đâu bạn !

Cách 1:
Thuật toán: Gán biến Max và Min bằng 1 giá trị bất kỳ trong mảng và dùng vòng lặp để sánh Max và Min với tất cả các giá trị còn lại trong mảng, nếu có giá trị nào lớn hơn cả Max hoặc nhỏ hơn cả Min thì cập nhật giá trị đó và Max và Min, cứ như thế cho đến khi kết thúc vòng lặp sẽ tìm được giá trị Max và Min

Cách 2:
Thuật toán: Gán biến Max với giá trị bé nhất có thể và biến Min với giá trị lớn nhất có thể. Vậy giá trị lớn nhất và bé nhất là gì ?
Bạn #include <limits.h> và gán Max = INT_MIN và Min = INT_MAX nhé !
Sau đó vẫn dùng vòng lặp duyệt mảng, nếu giá trị nào bé hơn cả Min hay lớn hơn cả Max thì cập nhật phần tử đó cho 2 biến Max và Min. Cuối cùng, ta sẽ tìm được Max và Min.

Ví dụ code của bạn khai báo mảng A gồm 10 phần tử thì cho vòng lặp chạy từ 0 đến 9 và làm như cách trên ! Còn lại bạn tự tìm hiểu và giải nhé

lethanhbinh1997 · June 14, 2016, 2:41am

Bài của mình là bắt buộc dùng đệ quy rồi bạn, mình hiểu cách của bạn rồi nhưng mà đề thì chỉ cho làm theo đệ quy thôi

tcm · June 14, 2016, 2:45am

Thế thì nhờ các member khác giúp chứ bài này dùng đệ quy cũng rối và mất thời gian mà mình lại không có thời gian

lethanhbinh1997 · June 14, 2016, 2:47am

vậy mình cảm ơn bạn đã giúp mình nha

chichi · June 14, 2016, 3:11am

Ý tưởng tìm min tại vị trí k là đã biết min của a[0] -> a[k-1] xong so sánh gía trị ấy với a[k] thằng nào bé hơn là min, bạn có thể debug để hiểu hơn

void · June 14, 2016, 4:03am

#include <iostream>
using namespace std;

#define MAX(x1, x2) (((x1) > (x2)) ? (x1) : (x2))
#define MIN(x1, x2) (((x1) > (x2)) ? (x2) : (x1))

int max(int *arr, int n)
{
  if (n == 2)
  {
    return MAX(arr[0], arr[1]);
  }

  return MAX(arr[n - 1], max(arr, n - 1));
}

int min(int *arr, int n)
{
  if (n == 2)
  {
    return MIN(arr[0], arr[1]);
  }

  return MIN(arr[n - 1], min(arr, n - 1));
}

int main()
{
  int arr[] = { 1, 7, 3, 4, 5, 6 };
  int a = max(arr, 6);
  int b = min(arr, 6);
  cout << a << b << endl;
  return 0;
}

Cu_Chuoi · June 14, 2016, 4:51am

Mình nói về Min nha, ban đầu đệ quy chạy từ trên xuống, phân tích thành các bài toán nhỏ nhất, đến khi Min(A,1) (ở đây là 4) thì sẽ chạy ngược lên đê so sánh
if (A[n - 1] < Min(A, n - 1)) return A[n - 1]; else return Min(A, n - 1);

reoteu_ray · June 14, 2016, 4:55am

mình thấy đệ quy là pp rất tốn bộ nhớ máy tính và cũng ít khi dùng đến nó , chương trình viết bằng đệ quy thì công nhận là gọn và ngắn thật nhưng tốc độ chạy và ngốn bộ nhớ stack của nó thì kinh khủng…

lethanhbinh1997 · June 14, 2016, 12:13pm

Cảm ơn bạn nhiều nha, cách của bạn hay quá

lethanhbinh1997 · June 14, 2016, 12:14pm

Mình đã hiểu cái code của mình rồi, cảm ơn bạn nhiều lắm nha

lethanhbinh1997 · June 14, 2016, 12:15pm

Cái này mình đang hỏi về đệ quy đó bạn, mình tìm được lời giải thích cho mình rồi, bạn tham khảo luôn nhé

lethanhbinh1997 · June 14, 2016, 12:15pm

Cái này có trong đề cương ôn thi của mình, mà khi ra đi làm thì đệ quy không được dùng nhiều hả bạn