Bài tập C

[nobita611]

Mình có bài này muốn mọi người gợi ý thêm
liệt kê tập con k phần tử
VD:
n=5
k=3
ta có
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

[sieuphuong]

Mình nghĩ như sau :

Thứ nhất : yêu cầu của bài toán là liệt kê các tập con k phần tử lấy từ n phần tử -> có tổ hợp chập k của n phần tử tập con . Từ đó ta có thể cấp phát động mà xây dựng một mảng 2 chiều gồm có k cột và kCn hàng ( trời ơi sao ko có chức năng sub & sup hả anh Dr thân yêu của em ơi ) . Mảng này chứa các phần tử của các dãy . In mảng 2 chiều ra sẽ được kết quả như ý .

Thứ hai : để ý thấy rằng kết quả như ví dụ của bạn có tuân theo một quy luật nhất định nào đó :

1 2 3

Xét trong 1 dãy , giá trị của các phần tử là khác nhau và xếp theo thứ tự tăng dần .

1 2 3
1 2 4
1 2 5

Xét các dãy trên , ta thấy rằng dãy sau luôn tăng giá trị của phần tử phải nhất lên 1 đơn vị

1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Xét các dãy trên , ta thấy khi tăng giá trị của phần tử phải nhất lên = n rồi thì dãy lại tăng phần tử liền trái nó lên cho đến khi bằng n thì thôi và lại tăng tiếp phần tử liền trái nó nữa theo quy luật như vậy đến khi gặp phần tử trái nhất thì thôi . Chắc chắn 1 điều rằng số dãy sinh ra luôn = nCk . ^_^

[nobita611]

thanks bạn nhiều nhiều, nhưng đó là làm trên mảng 2 chiều, nếu làm trên mảng 1 chiều thì phải làm thế nào hả bạn.

[hoaxuyenchi]

Nếu bạn muốn làm trên mảng 1 chiều thì cũng không có gì khó cả. Bạn có thể tính được số phần tử sinh ra sẽ bằng tổ hợp chập k của n phần tử ( giả sử k<n). Cách đơn giản nhất là dùng k lệnh for lồng nhau, điểm xuất phát của for đầu là 1 và lệnh for sau sẽ xuất phát với giá trị hơn 1 đơn vị so với giá trị hiện tại của lệnh for phía trên và đích của cái đầu là = ((n-k)+1) ĐÍch của lệnh for sau sẽ hơn đích của lệnh for trước 1 đơn vị, Như vậy đích của lệnh for thứ k sẽ là n. Trong thân của lệnh for cuối cùng bạn gán giá trị cho mảng là được rồi.

[rox_rook]

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


void print_series(int *arr, int loop){
  for(int x = 0; x < loop; ++x){
    printf("%d", arr[x]);
  }
  printf("\n");
}

void find_series(int *arr, int times, int loop, int number){
  for(int j = arr[times - 1] + 1; j <= number - loop + times + 1; j++)
  {
    arr[times] = j;
    if(times == loop - 1)
      print_series(arr, loop);
    else
      find_series(arr, times + 1, loop, number);
  }
}

int main()
{
  int _mLoop, _mNumber;
  printf("How many element would you like: "); 
  scanf("%d", &_mNumber);
  printf("Enter a loop of element: ");
  scanf("%d", &_mLoop);
  int *arr = calloc(_mNumber, sizeof(int));
  
  for(int x = 0; x < _mNumber; ++x) 
    arr[x] = x + 1;

  find_series(arr, 0, _mLoop, _mNumber);
  
  free(arr);
  return 0;
} 

Kiếm sách của Lê Minh Hoàng trong box giải thuật, tập viết mấy bài còn lại cho quen !