Tổng hợp một số bài CODE TKTT

Chỉnh hợp ko lap chập k của n

Code:

/*
Liet ke Chinh hop ko lap  chap k cua n phan tu A[n,k]
*/

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

#define hs 50
int s[hs],n,k ;// mang s[] luu n phan tu ban dau
int x[hs],d=0; // mang x[] luu cac bo ket qua tim dc
int v[hs];    // mang v[] danh dau cac phan tu nao da dc chon rui 
char fi[]="Chinh_Hop.INP" ;
char fo[]="Chinh_Hop.OUT";

void Input()
{
    int tg =0 ;
    FILE *f = fopen(fi,"r");
    if(!f)
    {
          printf("\n\n Can't Open File ");
          getch();
          exit(0);
    }
    fscanf(f,"%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        {
              fscanf(f,"%d",&tg);
              s[i] = tg;
              v[i] =0; // khoi tao cho amng danh dau  =0 --chua dc chon
        }
    fclose(f);
}
void Display_Input()
{
    printf("\n\nKich thuoc mang so  la  : %d \n",n);

    for(int i=1;i<= n;i++)
          printf("%4d",s[i]);
}
void printResult(FILE *f)
{
        d++;
        fprintf(f,"%2d)",d);
        for(int i=1;i<=k;i++)
          {
                fprintf(f,"%4d ",x[i]);               
                printf("%4d",x[i]);
            }
          fprintf(f,"\n");
          printf("\n");
}

void Attempt(int i, FILE *f)
{
    for(int j=1; j<=n; j++)
    if(v[j] == 0 ) // chua dc chon 
      { 
            x[i]=s[j];
            v[j] = 1;
            if(i==k) printResult(f);
            else Attempt(i+1,f);
            v[j] = 0; // bo chon
      }
}

int main()
{
    x[0]=0;
    FILE *f= fopen(fo,"w");
    Input();
    Display_Input();
    printf("\n\n ket qua  : \n");
    Attempt(1,f);

    fclose(f);
    getch();
}

chỉnh hợp LẶP chap k của n phần tử

Code:

/*
Liet ke Chinh hop  LAP  chap k cua n phan tu A[n,k]
*/

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

#define hs 50
int s[hs],n,k ;// mang s[] luu n phan tu ban dau
int x[hs],d=0; // mang x[] luu cac bo ket qua tim dc
char fi[]="Chinh_Hop_Lap.INP" ;
char fo[]="Chinh_Hop_Lap.OUT";

void Input()
{
    int tg =0 ;
    FILE *f = fopen(fi,"r");
    if(!f)
    {
          printf("\n\n Can't Open File ");
          getch();
          exit(0);
    }
    fscanf(f,"%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        {
              fscanf(f,"%d",&tg);
              s[i] = tg;
        }
    fclose(f);
}
void Display_Input()
{
    printf("\n\nKich thuoc mang so  la  : %d \n",n);

    for(int i=1;i<= n;i++)
          printf("%4d",s[i]);
}
void printResult(FILE *f)
{
        d++;
        fprintf(f,"%2d)",d);
        for(int i=1;i<=k;i++)
          {
                fprintf(f,"%4d ",x[i]);               
                printf("%4d",x[i]);
            }
          fprintf(f,"\n");
          printf("\n");
}

void Attempt(int i, FILE *f)
{
    for(int j=1; j<=n; j++)
      { 
            x[i]=s[j];
            if(i==k) printResult(f);
            else Attempt(i+1,f);
      }
}

int main()
{
    x[0]=0;
    FILE *f= fopen(fo,"w");
    Input();
    Display_Input();
    printf("\n\n ket qua  : \n");
    Attempt(1,f);

    fclose(f);
    getch();
}

Xếp Hậu :

Code:

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

#define N 8
int a[N+1],b[N*2+1],c[N*2+1],x[N+1];
FILE * f;
int d=0;
int init()
{
    f= fopen("OUTPUT.TXT","wa");
    for(int i=1;i<=N;i++) 
            a[i]=b[i]=c[i]=1; // cac vi tri deu tu do
    for(int i=N+1;i<=2*N;i++) 
              b[i]=c[i]=1;
    for(int i=1;i<=N;i++)
              x[i]=0;  // mang chua nghiem  .
}
void inNghiem()
{
    d++;
    fprintf(f,"\n Nghiem %2d: ",d);
    printf("\n Nghiem %2d: ",d);
    for(int i=1;i<=N;i++)
    {
            fprintf(f,"(%d,%d)  ",i,x[i]);
            printf("(%d,%d)  ",i,x[i]);
    }
}

void XepHau(int i)
{
    int k = 0;
    for(int j=1;j<=N;j++)
    {
            if(a[j]==1 && b[i+j]==1 && c[i-j+8]==1 )
            {
                        x[i]=j; // con hau hang i nam o cot j
                        a[j]=0;b[i+j]=0;c[i-j+8]=0;
                        if(i==N) // thong bao tim thay nghiem & in nghiem
                        {    inNghiem();
                              a[j]=b[i+j]=c[i-j+8]=1 ;
                        }
                        else 
                        {
                            XepHau(i+1);
                            a[j]=b[i+j]=c[i-j+8]=1 ;
                            x[i]=0;
                        }
            }
    }
   
}
int main()
{
    printf("\n\n  8 Con Hau");
    init();
    XepHau(1);
    fclose(f);
    getch();
}

QHD : Tay -> Dong
/*******************************************************************************************
* Input : Cho 1 bảng số a[][]
Yeu cau tim 1 duong di tu ben trai bang sang ben phai bang sao cho tong cac so
tren hanh trinh la lon nhat .
* Ouput : Tìm 1 đường đi từ cột 1 -> cột n : tổng các số trên đưởng di là MAX

Thuật toán QHD như sau
L[i][j] : là tổng lớn nhất cảu các đường đi từ cột 1 tới ô (i,j)
Ta có công thức QHD :
L[i][j] = a[i][j] + MAX { L[i-1][j-1],L[i][j-1],L[i+1][j+1] }
Cơ sở QHD :
L[i][1] = a[i][1] ; -- Tại cột đầu tiên thì tổng đường đi mới chỉ có a[i][1]
L[0][j] = L[n+1][j] = 0 ;
********************************************************************************************/

Code:

#include
#include
#include
#define hs 20
int a[hs][hs],L[hs][hs],v[hs][hs],m,n ;

char fi[]="Tay_Dong.INP" ;
char fo[]="Tay_Dong.OUT" ;

void Input()
{
    int tg =0 ;
    FILE *f = fopen(fi,"r");
    if(!f)
    {
          printf("\n\n Can't Open File ");
          getch();
          exit(0);
    }
    fscanf(f,"%d%d",&m,&n);
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
        {
              fscanf(f,"%d",&tg);
              a[i][j] = tg;
        }
    fclose(f);
}
void Display_Input()
{
    printf("\n\nKich co ma tran so da cho  la  : %dx%d \n",m,n);
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
        {
              if(j==1) puts("\n");
              printf("%4d",a[i][j]);
        }
}
void inkq()
{
    printf("\n\nKich co ma tran phuong an  L[][] la  : %dx%d \n",m,n);
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
        {
              if(j==1) puts("\n");
              printf("%4d",L[i][j]);
        }
}

int init()
{
    for(int i=1;i<=m;i++)  /// cot dau cua bang phuong an L[i][j] = a[i][j]
        L[i][1] = a[i][1] ;
    for(int j=0;j<=n;j++)  // co so QHD
        L[0][j] = L[n+1][j] = 0 ;
}
int max(int a,int b,int c,int *t)
{
    int Max = 0, i_max =0;
    if(a>b )
    {
          Max = a;
          *t=1;
    }
    else {
              Max = b;
              *t=2;
        }
    if(Max < c )
    {
          Max = c;
          *t=3;
    }
   
    return Max;

}
void QHD()
{
    int t=0;
    int i,j ;
    for( j=2;j<=n;j++) // duyet lan luot cac cot - ke tu cot 2
      for(i=1;i<=m;i++)    // duyet lan luot cac phan tu tren cot do
      {
           
              L[i][j] = a[i][j] + max(L[i-1][j-1], L[i][j-1], L[i+1][j-1],&t) ;
              v[i][j] = i-2 + t;
      }
       
}
void output()
{
    int s ,i,j,imax=1 ;
    s = a[1][n] ;
    int x[hs],d=0;
    for( i=1;i<=m;i++) // dyet cot cuoi cung
      if(s
      {
            s = L[i][n] ; 
            imax= i;
      }
    i =imax ;
    j = n;
    printf("\n\n Hanh trinh MAX tim dc la  : Tong MAX = %d\n\n ",L[i][j]);
    while(j>0)
      {
            d++;
            x[d] = a[i][j];
            i = v[i][j]  ;
            j--;   
      }
    for(i=d; i>1; --i)
      printf("%4d - ",x[i]);
    printf("%4d  ",x[i]);
}
int main()
{
    Input();
    Display_Input();
    init();
    QHD();
    inkq();
    output();
    printf("\n\nHello world \n");
    getch();
}

Góp vui phát

Code:

// Bai toan cai tui
// So luong do vat la n
// a[i] la trong luong do vat, c[i] la gia tri do vat
// w la trong luong co the chua dc cua tui
// L[i][j] la gia tri cua tui khi khoi luong la j va xet xong do vat i

#include <stdio.h>
#include <conio.h>

int a[100], c[100], n;
int L[100][1000];
int w;
FILE *fi,*fo;
char f1[]="caituiinput.txt";
char f2[]="caituioutput.txt";

void input()
{
    fi=fopen(f1,"r");
   
    if (fi)
    {
            fscanf(fi,"%d%d",&n,&w);
            for (int i=1;i<=n;i++)
                    fscanf(fi,"%d%d",&a[i],&c[i]);
        }
    fclose(fi);
 }
 
 int max(int x,int y)
 {
      return x>y?x:y;
  }
 
 void solve()
 {
      int i,j;
      // khoi tao L
      for (i=0;i<=n;i++)
          for (j=0;j<=w;j++)
              L[i][j]=0;
     
      // fix L
      for (i=1;i<=n;i++)
          for (j=1;j<=w;j++)
              {
                if (a[i]<=j) L[i][j]=max(L[i-1][j],L[i-1][j-a[i]]+c[i]);
                else        L[i][j]=L[i-1][j];
              }
  }
 
 void output()
 {
      int vmax, v;
      int i,j;
     
      fo=fopen(f2,"w+");
     
      if (fo)
      {
            vmax=0; // max value = 0
            v=0;    // trong luong cua tui khi dat max value
           
            // tim ra max value voi trong luong < w
            for (j=1;j<=w;j++)
                if (vmax<L[n][j])
                    {
                      vmax=L[n][j];
                      v=j;
                      }
            j=v;
            // save to file
            fprintf(fo,"%d\n",vmax);
            for (i=n;i>=1;i--)
                if (L[i][j]!=L[i-1][j]) // khi ma i dc cho vao tui
                    {
                      fprintf(fo,"%d% 4d% 4d\n",i,a[i],c[i]);
                      j=j-a[i];
                      }
        }
      fclose(fo);
  }
 
  int main()
  {
      input();
      solve();
      output();
     
      printf("ok !");
      getch();
  }

Thêm phát nữa cho máu : Khoảng cách xâu

Code:

// Bien doi xau - tim khoang cach giua hai xau
// X, Y la hai xau cho truoc, tim khoang cach hai xau nay
// L[i][j] la khoang cach giua hai xau con x[]1..i] va y[1..j]
// Neu xi=yj thi L[i,j]=L[i-1,j-1]
// Neu xi!=yj thi : L[i][j]=min(L[i-1][j]+1,L[i][j-1]+1,L[i-1][j-1]+1);
// Khoi tao L[i,0]=i; i : 0-> M
// Khoi tao L[0,j]=j; j : 0-> N
// L[m][n] la khoang cach can tim
// Neu xi=yj thi giam i va j, neu nguoc lai thi L[i][j]=L[i-1][j]+1

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

char s1[100],s2[100];
int len1, len2;
int L[100][100];
FILE *fi,*fo;
char f1[]="kcxinput.txt";
char f2[]="kcxouput.txt";

void input()
{
    fi=fopen(f1,"r");
   
    if (fi)
    {
            fscanf(fi,"%s%s",&s1,&s2);
            len1=strlen(s1);
            len2=strlen(s2);
        }
    fclose(fi);
 }
 
 int min(int x,int y,int z)
 {
    int t=x<y?x:y;
    return t<z?t:z;
 }
 
 int nh(int i,int j) // khoang cach hia hai xau con co do dai i va j
 {
    if (s1[i]==s2[j]) L[i][j]=L[i-1][j-1];
    else L[i][j]=min(L[i-1,j]+1,L[i][j-1]+1,L[i-1][j-1]+1);
    return L[i][j];
 }
 
 void process()
 {
      int i.j;
      int phu[100];
      int count;
     
      i=len1;
      j=len2;
      count=0;
      fo=fopen(f2,"w+");
     
      if (fo)
      {
      while(i>0&&j>0) // thuc hien neu chua bien doi xong
      {
          if (s[i]=s[j]) { i--; j-- }
          else
            {
              count++; // so cho can bien doi
              if (L[i][j]==L[i-1][j-1]+1) // phep thay the
                  {
                    fprintf(g,"R  %d  %d\n",i,a[j]);
                    i--; j--;
                  }
              else
                  {
                  if (L[i][j]==L[i-1][j]+1) // phep xoa
                  {
                      fprintf(g,"D  %d\n",i);
                      i--;
                  }
                  else
                      if (L[i][j]=L[i][j-1]+1) // phep chen
                      {
                        fprintf(g,"I  %d  %d\n",i+1,s2[j]);
                      }
                  }
            }
      }  // end of while
     
      while (j>0)
            {
                  fprintf(g,"I  %d  %d\n",1,s2[j]);
                  i--;
                  count++;
            }   
     
      while(i>0)
                {
                  fprintf(g,"D  %d\n",i);
                  i--;
                  count++;
                }
     
      fprintf(g,"%d",count);
      }
      fclose(fo);
  }
 
  int main()
  {
      input();
     
      for (int i=0;i<=len1;i++)
          for (int j=0;j<=len2;j++)
              L[i][j]=0;
             
      for (int i=0;i<=len1;i++)
          for (int j=0;j<=len2;j++)
              L[i][j]=nh(i,j);
      process();
     
      printf("ok!");
      getch();
  }

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define true 1
#define false 0
int n,k;
int *a,*c;
void khoitao()
{
printf("n:= "); scanf("%d",&n);
printf("k:= "); scanf("%d",&k);
a=(int *)calloc(n,sizeof(int));
c=(int *)calloc(n,sizeof(int));
for(int i=1;i<=n;i++)
*(c+i)=true;
}
void PrintResult()
{
int i;
for(i=1;i<k;i++)
printf("%3d , ",*(a+i));
printf("%3d\n",*(a+k));
}
void Try(int i)
{
int j;
for(j=1;j<=n;j++)
if(*(c+j)==true)
{
*(a+i)=j;
if(i==k)
PrintResult();
else
{
*(c+j)=false;
Try(i+1);
*(c+j)=true;
}
}
}
int main()
{
khoitao();
Try(1);
getch();
}

Chào các bạn. Thấy mọi người bàn tán sôi nổi quá. Mình rất cảm on các bạn. Nhân đây mình xin đóng góp bài Độ lệch của dãy số sử dụng thuật toán chia để trị

THuật giải sơ lược như sau

Diff(i, j) = max {diff(i,k); diff(k, j) ; Max[k, j] - Min [i, k]}

Trong đó k = [(i+j)/2],
Max[i, j] là số lớn nhất trong đoạn từ i tới j
Min[i, j] là số nhỏ nhất trong đoạn từ i tới j

Chương trình:

Code:

/*
        Chuong trinh tinh do lech cua day so
       
        Bai toan: Diff(A)= max{aj- ai, 1<= i <= j<= n}
*/

#include iostream


using namespace std;
int a[100];
int n;
int Max[100][100];
int Min[100][100];

int enter()
{
    int i;
    scanf("%d", &n);
    for(i=0; i
      scanf("%d", &a[i]);
    return n;
}

int getMin(int first, int last)
{
    int i;
    int min= a[first];
    for(i = first + 1; i <= last; i ++)
      if(a[i] < min)
          min= a[i];
   
    return min;
}

int getMax(int first, int last)
{
    int i;
    int max= a[first];
    for(i = first + 1; i <= last; i ++)
      if(a[i] > max)
          max= a[i];
   
    return max;
}

void min_max()
{
    int i, j;
    for(i = 0; i < n; i ++)
      for(j = i; j < n; j++)
          {
            Max[i][j]= getMax(i, j);
            Min[i][j]= getMin(i, j);
          }
}

int chooseMax(int x, int y, int z)
{
    int max= x;
    if(max < y)max = y;
    if(max < z)max = z;
    return max;
}

int diff(int first, int last)
{
    if(first == last)return 0;
    else if(last - first == 1)return a[last] - a[first];
    else {
                int mid= (first + last)/2;
                return chooseMax(diff(first, mid), diff(mid, last),
                                          Max[mid][last] - Min[first][mid]);
        }
}

int main()
{
    freopen("diff.inp","r", stdin);
    n= enter();
    min_max();
    int result= diff(0, n-1);
    cout<
    system("pause");
   
}

Có ai biết đề của bài toán lát nền không. Tìm mãi mà chẳng thấy đề bài.

Trong danh sach bai tap co bai 30 la 1 bai lat nen day. Lat gach search google dc nhieu hon. Ko co Unikey

Các pác xem 2 bài này nè,thi sẽ vào...hoho...Nam nhi đại trượng phu nói 1 là 1...2 là...3...haha

/*
De bai:
Cho 2 day X (M phan tu) va Y (n phan tu)
Tim day con chung dai nhat cua 2 day

Input:
M
X[1]...X[M]
N
Y[1]...Y[N]

Output:
K - do dai day con dai nhat
Day con chung dai nhat
*/
#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
#define INPUT_FILE "DayConChungDaiNhat.txt"
int n,m,C[100][100],X[100],Y[100];
void docDuLieu(){
FILE *file;
file = fopen(INPUT_FILE, "r");

if(file != NULL){
fscanf(file,"%d", &m);
for(int i=1; i<=m; i++)
fscanf(file, "%d", &X[i]);
fscanf(file, "%d", &n);
for(int i=1;i<=n;i++)
fscanf(file, "%d", &Y[i]);
}
else{
puts("Khong tim thay file!");
getch();
exit(0);
}
}
void inDuLieu(){
puts("Day X:");
for(int i=1; i<=m; i++)
printf("%d ", X[i]);
puts("");

puts("Day Y:");
for(int i=1; i<=n; i++)
printf("%d ", Y[i]);
puts("");

}
void BangPhuongAn()
{
int i,j;
for(i=0;i<=m;i++)
C[i][0]=0;
for(j=0;j<=n;j++)
C[0][j]=0;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
if(X[i]==Y[j])
C[i][j]=C[i-1][j-1]+1;
else {
C[i][j]=C[i-1][j];
if(C[i][j-1]>C[i-1][j])
C[i][j]=C[i][j-1];
}
}
}
void TruyVet()
{
int i,j;
i=m;
j=n;
while(i>0&&j>0){
if(X[i]==Y[j]){
printf("%6.1d",X[i]);
i=i-1;j=j-1;
}
else {
if(C[i-1][j]>C[i][j-1])
i=i-1;
else j=j-1;
}
}
}
int main()
{
int i,j;
docDuLieu();
inDuLieu();
BangPhuongAn();
printf("Do dai day con chung dai nhat la: %d \n",C[m][n]);
if(C[m][n]>0){
printf("Day con chung dai nhat la (in nguoc tu cuoi len): \n");
TruyVet();
}
else
puts("Hai day khong co day con chung !");
getch();
return 0;
}
//////////////////////Xếp ba lô///////////////////
*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define INPUT_FILE "XepBaLo01.txt"
int n, w, c[50][50], p[100], v[100] ;
void docDuLieu(){
FILE *file;
file = fopen(INPUT_FILE, "r");
if(file != NULL){
fscanf(file, "%d", &n);
for(int i=1; i<=n; i++){
fscanf(file, "%d %d", &p[i], &v[i]);
}
fscanf(file, "%d", &w);
}
else{
puts("Khong tim thay file!");
getch();
exit(0);
}
}
void inDuLieu(){
for(int i=1; i<=n; i++){
printf("Vat thu %d: (%d, %d)\n", i, p[i], v[i]);
}
printf("Gioi han cua ba lo: %d\n\n", w);
}
void dungBangPhuongAn(){
for(int i=0; i<=n; i++){
c[i][0]=0;
}
for(int j=0; j<=w; j++){
c[0][j]=0;
}

for(int i=1; i<=n; i++){
for(int j=1; j<=w; j++){
c[i][j] = c[i-1][j];
if(p[i]<=j){
if(c[i-1][j-p[i]]+ v[i] > c[i][j] ){
c[i][j]= c[i-1][j-p[i]]+v[i];
}
}
}
}
}
void truyVet(){
int i=n, j=w;
if(c[n][w]>0){
while(i>0&& j>0){
if(c[i][j]==c[i-1][j-p[i]]+v[i]){
printf("Su dung vat thu %d: (%d, %d) \n", i, p[i], v[i] );
j-=p[i];
}
i--;
}
}
printf("Gia tri lon nhat la: %d\n", c[n][w]);
}
int main(){
docDuLieu();
inDuLieu();
dungBangPhuongAn();
truyVet();

puts("Hoan thanh!");
getch();
return 0;
}

không thi vào dãy con chung dài nhất đâu, đề cương không có bài này mà

QHD có 4 bài thì nó là 1 trong 4 bài đó...kakaka

Tiên đoán...sẽ vào bài
1.Xâu ABC(Nhánh cận).
2.Ba lô(QHD).
3.Xâu con chung dài nhất(QHD).

Lý thuyết vào Quay lui hoặc Tham Lam....Hôm qua mới đi uống rượu với thày xong...kakakaka

sao lung tung hết cả vậy. Cho để nằm trong đề cương chứ. Nếu chắc chắn thì post lên nha. Còn theo đề cương thì có 2 bài. Một lý thuyết và một bài tập. Trong đó bài tập nào cũng quan trọng vào xác xuất vào như nhau

Hôm nay tớ post bài toán sắp xếp trộn cho các bạn. Về ý
tưởng thì các bạn tìm trực tiếp trên mạng. Tớ chỉ nói sơ qua thuật toán thôi.
Tất nhiên là sử dụng pương pháp chia để trị rùi.
Ý tưởng: Mỗi đoạn (i,j) ta chia đôi đoạn đó ra và thực hiện trên 2 đoạn con đó, sau khi thực hiện ta ghép 2 đoạn vào 1 theo hướng phần tử bé hơn đứng trước, phần tử lớn hơn đứng sau.


Chương trình:

Code:

/*
    Chuong trinh sap xep chon
*/

#include"iostream"


using namespace std;

int a[100];
int n;

int c[100];

int enter()
{
    int i;
    cin>>n;
    for(i = 0; i < n; i ++)
      cin>>a[i];
    return n;
}

void merge(int first, int mid, int last)
{
    int b[100];
    int k=first;
    int i= first, j= mid + 1;
    while(i <= mid && j <= last)
        {
            if(a[i] < a[j])
              b[k++]= a[i++];
            else
              b[k++]= a[j++];
        }
    if(i <= mid)
      for(int i1= i; i1 <= mid; i1 ++)
          b[k++]= a[i1];
    else
      for(int j1= j; j1 <= last; j1 ++)
          b[k++]= a[j1];
   
    for(i = first; i <= last; i ++)
        a[i] = b[i];
}

void mergeSort(int first, int last)
{
    if(first == last)return;
    else
      {
              int mid= (first + last)/2;
              mergeSort(first, mid);
              mergeSort(mid + 1, last);
              merge(first, mid, last);
      }
}

void show()
{
    int i;
    for(i = 0; i < n; i++)
      cout<<<"  ";
    cout<
}

int main()
{
    freopen("merge.inp", "r", stdin);
    n= enter();
    show();
    mergeSort(0, n-1);
    show();
    system("pause");
}

hihi, vào đây thấy toàn các "gia cát dự" dự đoán đề thi thui. ai có code mấy bài nhánh cận thì post cho mình tham khảo với

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

#define MAX 20

int n, P[MAX], B[MAX], C[20][20], count=0;
int A[MAX], XOPT[MAX]; // XOPT[] : Hanh trinh toi uu
int can, cmin, fopt; // fopt : chi phi toi uu

void Read_Data(void)
{
int i, j;
FILE *fp;
fp = fopen("NguoiDuLich.inp","r");
if (!fp) printf("\n Khong mo duoc file NguoiDuLich.inp");
fscanf(fp,"%d", &n);
printf("\n So thanh pho: %d", n);
printf("\n Ma tran chi phi:");
for (i=1; i<=n; i++)
{
printf("\n");
for(j=1; j<=n; j++)
{
fscanf(fp,"%d",&C[i][j]);
printf("%5d", C[i][j]);
}
}
fclose(fp);
}

int Find_C_Min(void)
{
int min=1000, i, j; //gan chi phi thap nhat la 1000
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if (i!=j && min>C[i][j])
min=C[i][j];
}
}
return(min);
}

void Init(void)
{
int i;
cmin=Find_C_Min();
fopt=32000;
can=0;
A[1]=1;
for (i=1;i<=n; i++)
B[i]=1;
}

void Result(void)
{
int i;
printf("\n\n Chi phi toi uu: %d", fopt);
printf("\n\n Hanh trinh:");
for(i=1; i<=n; i++)
printf("%3d ->", XOPT[i]);
printf(" %d",1);
}

void Swap(void)
{
int i;
for(i=1; i<=n;i++)
XOPT[i]=A[i];
}

void Update_Kyluc(void)
{
int sum;
sum=can+C[A[n]][A[1]];
if(sum<fopt)
{
Swap();
fopt=sum;
}
}

void Try(int i)
{
int j;
for(j=2; j<=n;j++)
{
if(B[j])
{
A[i]=j; B[j]=0;
can=can+C[A[i-1]][A[i]];
if (i==n) Update_Kyluc();
else if( can + (n-i+1)*cmin< fopt)
{
count++;
Try(i+1);
}
B[j]=1;
can=can-C[A[i-1]][A[i]];
}
}
}

int main()
{
printf("\n______________THUAT TOAN NHANH CAN________________");
printf("\n\n Bai toan: NGUOI GIAO HANG ");
printf("\n\n Mot nguoi can phai giao hang tai N thanh pho, voi chi phi di lai khac nhau");
printf("\n Tim hanh trinh thoa man: ");
printf("\n\t Di qua tat ca cac thanh pho. \n\t Moi thanh pho chi qua dung mot lan. \n\t Chi phi di lai la nho nhat");
printf("\n\n Bai giai:\n");
Read_Data();
Init();
Try(2);
Result();
getch();
}

doc di roi co ma hieu

thank con nhìu nhìu . mà m phân tích luôn cả độ phức tạp đi :P

Tình hình là ngoài mấy bài của thằng Nghĩa là chuẩn xác chắc là test trước khi gửi còn lại các bài khác có rất nhiều lỗi.Còn về vấn đề thi vào bài gì thì cứ phần nào tớ học nó sẽ không vào.Bây giờ tớ vẫn chưa học gì.

Hoàng thân mến!
Hoàng nên đọc kỹ code một chút. Tớ biết là chắc chắn có người thắc mắc tại sao nó lại không chạy. Có những nguyên nhân sau
1. Phải có file input có tên trùng với tên chương trình đưa ra, hoặc đã có file input rùi nhưng chương trình của tớ xuất ra file output, chắc Hoàng không để ý.

2. Khi gửi bài một số ký tự đặc biệt không được trình duyệt show ra, chẳng hạn như ký tự mở ngoặc và đóng ngoặc nhọn, trình duyệt sẽ dịch nó là code html và hiển nhiên là không show lên được.
Để chạy được thì khai báo thư viện là iostream, các câu lệnh cout sửa một chút vì có ký tự đặc biệt khác

cuongcnb đã viết:

Hoàng thân mến!
Hoàng nên đọc kỹ code một chút. Tớ biết là chắc chắn có người thắc mắc tại sao nó lại không chạy. Có những nguyên nhân sau
1. Phải có file input có tên trùng với tên chương trình đưa ra, hoặc đã có file input rùi nhưng chương trình của tớ xuất ra file output, chắc Hoàng không để ý.

2. Khi gửi bài một số ký tự đặc biệt không được trình duyệt show ra, chẳng hạn như ký tự mở ngoặc và đóng ngoặc nhọn, trình duyệt sẽ dịch nó là code html và hiển nhiên là không show lên được.
Để chạy được thì khai báo thư viện là iostream, các câu lệnh cout sửa một chút vì có ký tự đặc biệt khác

oh yeah, đúng thế, code bị thay đổi khi post lên, chạy hay khong quan trọng gì, quan trọng là ý tưởng, mai thi trên giấy mà

:)
AE cố gắng nhé, quyết tâm đạt điểm cao

phen này quyêt tâm ko gặp lại nao~ nghiện thuốc 'phiện' nữa :D
'

VoTienKhoangHau đã viết:

:)
AE cố gắng nhé, quyết tâm đạt điểm cao

phen này quyêt tâm ko gặp lại nao~ nghiện thuốc 'phiện' nữa :D
'

ok men

Bài của cường viết bằng C++ thì tớ biết rùi có thể lúc chuyển sang C to chuyển sai 1 chỗ nào đó 3 năm ko sờ đến C++ mà.Còn Chiến xem lại hộ bài xâu cái hôm qua chạy 1 phát ra file txt 1,5gb chưa đọc lại xem vì sao nữa.Tớ nghĩ là mai thi trên giấy thì ko cần chuẩn lắm thì đúng rồi nhưng pót bài trên mạng các bạn sẽ test và nếu thấy không đúng thì có thể sẽ không nghĩ là ý tưởng đó đúng .Bài Cường input output tớ làm khác mà còn cái lỗi nó thông báo tớ còn chẳng hiểu la cái lỗi gì cơ.

ờ, bài cái túi mình test chạy ngon lành rồi, vài biến đổi xâu thì t code tren dev C, code vội vàng cho cho lên diễn đànm ý tương thì chính xác rồi, nhwung code chưa test ;))

Nhân đây tớ xin đưa ra chương trình bài toán lát nền.
Đề bài như sau (câu 27):






Lát gạch: Cho một nên nhà hình vuông có
kích thước 2^k bị khuyết một ô., hãy tìm cách lát nền nhà bằng
loại gạch hình thước thợ (lát được 3 ô cùng lúc).





Mình lấy thuật toán của bạn Lê
Hoàng Hải, lớp 10 chuyên tin, Đại học Khoa học Tự nhiên, ĐHQGHN và đã chuyển
hóa thuật toán thành chương trình.


Để phân biệt 2 viên gạch khác
nhau, ta sẽ đánh màu bằng số, ví dụ 2 viên gạch gần nhau ta sẽ cho viên thứ nhất
màu 1, viên thứ 2 màu 2.


Dễ dàng chứng minh được rằng chỉ
cần 3 màu 1, 2, 3 ta có thể tô hết.


Vì với n= 2^k nên mới có thuật
toán tốt, nếu các trường hợp khác phải dùng vét cạn.


Xét trường hợp đơn giản k=1, ô
vuông có độ dài bằng 2, ta chỉ cần lát một viên và còn thiếu một ô (thỏa mãn
bài toán)






Với mỗi ô vuông với cạnh lớn hơn
2 ta sẽ chia ra làm 4 phần, trong đó phần đáy bên trái ta đã xây dựng, để xây dựng đáy phải và trên trái ta chỉ cần lật ngược nền và chuyển 1 thành 3 và 3 thành 1 (4 - a[i][j]). Còn trên phải thì ta tịnh tiến.

Lát lên trên:


Lát sang phải

Lát chéo:




Bài toán lát nền:

Code:

#include
#include

using namespace std;
int n; // do dai cua nen nha
int a[101][101];  //mang luu vi tri cua o tren nen nha


void diagonal(int start)
{
    int i, j, v;
    v= n- start + 1;
    for(i = start; i <= n; i ++)
      for(j = 1; j <= v; j ++)
        a[i-v][j+v] = a[i][j];
}

void right(int start)
{
    int i, j, v, v2;
    v= n- start + 1;
    v2= 2*v;
    for(i = start; i <= n; i ++)
      for(j = 1; j <= v; j ++)
        a[i][v2 - j + 1] = 4 - a[i][j];
}

void up(int start)
{
    int i, j, v, v2;
    v= n- start + 1;
    v2= n - 2*v + 1;
    for(i = 0; i < v; i ++)
      for(j = 1; j <= v; j ++)
        a[v2+i][j] = 4 - a[n-i][j];
}

void fill(int start)
{
    if(n- start > 1)fill((n + start)/2 + 1);
    diagonal (start);
    up(start);
    right(start);
}

void init()
{
    a[n-1][1] = 1;
    a[n-1][2] = 2;
    a[n][1] = a[n][2] = 1;
}

void show()
{
    int i, j;
    for(i = 1; i <= n; i++)
      {
          cout<
          for(j = 1; j <= n; j ++)
            cout<<<"  ";
      }     
}

int main()
{   
    cin>>n;
    init();
    fill(n/2 + 1);
    show();
    getch();
}

Cam on Cuong!
Thuat toan nay don gian va de hieu! vay ma search tren mang chang thay dau ca! ah? chieu mai neu co the thi thi xong cho to hoi mot chut OTOMAT nha!
Thanks!