Lỗi khó hiểu trong c khi đệ quy

Mình có làm cái bài

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

void DeQuyFind(int sodachon,int NumberCh[], int x, int y, int ArrayThis[], int kc, int MaxPagara);

main(){
	//Setup data
	FILE *fp;
   fp = fopen("FIBSEQ.inp", "r");
   char Nik[10];
   fgets(Nik, 10, (FILE*)fp);
   int ENik = atoi(Nik);
   
   int MangDateE[ENik*3];
   int MaxPagara=0;
   for(int i=0;i<ENik*3;i+=3){
   char StringIn[255];
   fscanf(fp, "%s", StringIn);
   MangDateE[i]=atoi(StringIn);

   fscanf(fp, "%s", StringIn);
   MangDateE[i+1]=atoi(StringIn);
   
   if(MaxPagara<(MangDateE[i]+MangDateE[i+1]-1))
   MaxPagara=MangDateE[i]+MangDateE[i+1]-1;

   fscanf(fp, "%s", StringIn);
   MangDateE[i+2]=atoi(StringIn);
	}
   fclose(fp);
   //processing
   int PagaHu[MaxPagara];
   for(int i=0;i<MaxPagara;i++){
   		if(i==0 || i==1)
	   PagaHu[i]=1;
	   else
	   PagaHu[i]=PagaHu[i-1]+PagaHu[i-2];
	   
	   printf("%i, ",PagaHu[i]);
   }
   //processing 2
   for(int i=0;i<ENik*3;i+=3){
   	int beta[MangDateE[i]];
   	DeQuyFind(0,beta,MangDateE[i+1],MangDateE[i],PagaHu,MangDateE[i+2],MaxPagara);
   }
}

int * CopyArray(int MDS[],int count);
int * CopyArray(int MDS[],int count){
	int MDS2[count-1];
	int Valuc =0;
	for(int i=0;i<count;i++){
		if(MDS[i]!=0){
			MDS2[Valuc]=MDS[i];
			Valuc++;
		}
	}
	return MDS2;
}

void DeQuyFind(int sodachon,int NumberCh[], int x, int y, int ArrayThis[], int kc, int MaxPagara){
	if((y-x)>=1){
	for(int i=(x-1);i<=y;i++){
		int DScs=MaxPagara-sodachon;
		if(i==y)
		NumberCh[sodachon]=0;
		else{
		NumberCh[sodachon]=ArrayThis[i];
		ArrayThis[i]=0;
		DScs--;
		}
		
	DeQuyFind(sodachon+1,NumberCh,x,y-1,CopyArray(ArrayThis,DScs),kc,MaxPagara);
	}
	} else {
		int SumOf=0;
		int RealCountOf=0;
		for(int i=0;i<sodachon;i++){
		SumOf+=NumberCh[i];
		if(NumberCh[i]!=0)
		RealCountOf++;
		}
		if((SumOf%kc)==0){
			//print result
			FILE *fp;
			fp = fopen("FIBSEQ.out", "a");
			fprintf(fp,"%i ",RealCountOf);
			for(int i=0;i<sodachon;i++){
			if(NumberCh[i]!=0)	
			fprintf(fp,"%i ",NumberCh[i]);
			}
			fprintf(fp,"\n");
			fclose(fp);
		}
	}
}

Nhưng khi chạy thì nó ra những con số khó hiểu

6 2 3 6486656 6486544 5 6486320 
6 2 3 6486656 6486544 5 6486320 
5 2 3 6486656 6486544 6486208 
5 2 3 6486656 6486544 6486208 
5 2 3 6486656 6486432 6486320 
5 2 3 6486656 6486432 6486320 
5 2 3 6486656 3 5 
5 2 3 6486656 5 3 
5 2 3 6486656 5 3 
5 2 3 6486656 5 3 
5 2 3 6486656 5 3 
5 2 3 6486656 3 5 
7 2 3 6486656 4 5 3 5 
6 2 3 6486656 4 6 6486208 
5 2 3 6486656 6486432 6486320 
5 2 3 6486656 6486432 6486320 
5 2 3 6486656 3 5 
5 2 3 6486656 5 3 
5 2 3 6486656 5 3 
5 2 3 6486656 5 3 
5 2 3 6486656 5 3 
5 2 3 6486656 3 5 
6 2 3 6486656 6486960 6486320 12 
5 2 3 6486656 6486960 5 
5 2 3 6486656 6486960 5 
5 2 3 6486656 6486960 5 
5 2 3 6486656 6486960 5 
6 2 3 6486656 6486960 6486320 12 
5 2 3 6486656 6486432 6486320 
5 2 3 6486656 6486432 6486320 
5 2 3 6486656 3 5 
5 2 3 6486656 5 3 
5 2 3 6486656 5 3 
5 2 3 6486656 5 3 
5 2 3 6486656 5 3 
5 2 3 6486656 3 5 
4 2 3 6486544 3 
4 2 3 6486544 3 

Dầu vào

2
10 3 9
9 2 3

Chưa xét đúng sai, bạn ghi luôn trong hàm tìm là thấy bất ổn rồi. Và đó là đệ quy nên ghi vô số thế đấy.

2 Likes

Nếu số phần tử dãy >= modulo thì ta không có gì để xét nữa.

Xét các suffix sum của dãy đã cho. Áp dụng Dirichlet suy ra có ít nhất hai phần tử trong mảng này đồng dư :smiley:

Vậy bài này O(n + log(i)) với O(k) mem.

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?