Thảo luận bài tập ôn luyện Olympic- Thuật Toán

09520500 · 14 Tháng Sáu 2011 18:04

Maximum
Consider the sequence of numbers ai, i = 0, 1, 2, …, which satisfies the following requirements:
a0 = 0
a1 = 1
a2i = ai
a2i+1 = ai + ai+1
for every i = 1, 2, 3, … .
Write a program which for a given value of n finds the largest number among the numbers a0, a1, …, an.
Input
You are given several test cases (not more than 10). Each test case is a line containing an integer n (1 ≤ n ≤ 99 999). The last line of input contains 0.
Output
For every n in the input write the corresponding maximum value found.
Sample
input output
5 3
10 4
0
Nguồn: http://acm.timus.ru/problem.aspx?space=1&num=1079
Bài này mình giải như sau nhưng không hiểu sai đâu?? Mọi người chỉ giáo nhé!

#include <iostream>
using namespace std;
int main()
{
long n,i=0,i_f=2;
long arr[10], f[99999];
f[0]=0; f[1]=1;
do
{
cin>>n;
while(n>=i_f)          //f(n) chua dc tinh
{
if(i_f%2==0)
f[i_f]= f[i_f/2];
else
f[i_f]= f[i_f/2]+f[i_f/2+1];
i_f++;
}
if(n%2==0) arr[i++]=f[n-1];
else arr[i++]=f[n];
} while(n!=0);
for(int j=0;j<i-1;j++)
cout<<arr[j]<<endl;
cin.get();
cin.get();
return 0;
}

07520004 · 14 Tháng Sáu 2011 19:05

[QUOTE=09520500;1998]Nguồn: http://acm.timus.ru/problem.aspx?space=1&num=1079
Bài này mình giải như sau nhưng không hiểu sai đâu?? Mọi người chỉ giáo nhé!

#include <iostream>
using namespace std;
int main()
{
long n,i=0,i_f=2;
long arr[10], f[99999];
f[0]=0; f[1]=1;
do
{
cin>>n;
while(n>=i_f)          //f(n) chua dc tinh
{
if(i_f%2==0)
f[i_f]= f[i_f/2];
else
f[i_f]= f[i_f/2]+f[i_f/2+1];
i_f++;
}
if(n%2==0) arr[i++]=f[n-1];
else arr[i++]=f[n];
} while(n!=0);
for(int j=0;j<i-1;j++)
cout<<arr[j]<<endl;
cin.get();
cin.get();
return 0;
}

[/QUOTE]
Nó ý tưởng đi em, thảy cái cục code dài ngoằng mà không có comment này thì chả ma nào đọc cho đâu

08520195 · 14 Tháng Sáu 2011 19:13

f[i_f]= f[i_f/2]+f[i_f/2+1]
f[i_f] = f[i_f/2]+f[i_f/2] + 1
nếu hiểu a(2i+1) = a(i) + a(i)+1

08520522 · 15 Tháng Sáu 2011 06:02

Vài chỗ chưa đúng:

i_f phải reset lại giá trị 2 mỗi vòng lặp while
Nên dùng biến Max để tìm giá trị lớn nhất, (hai giá trị cuối cùng không phải là lớn nhất, thử với n = 16).

09520500 · 17 Tháng Sáu 2011 23:29

[QUOTE=08520522;2015]Vài chỗ chưa đúng:

i_f phải reset lại giá trị 2 mỗi vòng lặp while
Nên dùng biến Max để tìm giá trị lớn nhất, (hai giá trị cuối cùng không phải là lớn nhất, thử với n = 16).[/QUOTE]
-> i_f ko cần phải reset lại vì chỉ cần tính f* 1 lần và lưu nó vào mảng rùi! Tính rùi ko cần tính lại
Em phát hiện quy luật sai! cứ tưởng là 1 trong 2 số cuối là Max!

10520180 · 19 Tháng Sáu 2011 17:54

Đây là bài em làm, có gì sai anh góp ý nha.

#include <stdio.h>
#include <stdlib.h>
const char *INP="MAX.INP";
const char *OUT="MAX.OUT";
int Maximum(int n);
void QuickSort(int a[],int l, int r);
void QuickSort(int a[],int l, int r)
{
int i,j,x,temp;
i=l;
j=r;
x=a[(l+r)/2];
do{
while(a*<x) i++;
while(a[j]>x) j--;
if(i<=j)
{
temp=a*;
a[j]=a*;
a[j]=temp;
i++;
j--;
}
}while(i<=j);
if(l<j) QuickSort(a,l,j);
if(i<r) QuickSort(a,i,r);
}
int Maximum(int n)
{
int a[100000];
int i;
a[0]=0;
a[1]=1;
for(i=1;i<=n/2+1;i++)
{
a[2*i]=a*;
a[2*i+1]=a*+a[i+1];
}
QuickSort(a,0,n);
return a[n];
}
void main()
{
int a[100000];
int i,n=0;
FILE *fi=fopen(INP,"r");
do
{
fscanf(fi,"%d",&a[n]);
if(a[n]<=0) break;
else n++;
}while(1);
fclose(fi);
FILE *fo=fopen(OUT,"w");
for(i=0;i<n;i++) fprintf(fi,"%d
",Maximum(a*));
fclose(fo);
}

08520059 · 19 Tháng Sáu 2011 18:05

Đã thử submit code ở trên nhưng bị wrong test 5. Tác giả bên trên có submit chưa vậy.:mad:

10520180 · 20 Tháng Sáu 2011 14:23

sau một đêm mày mò em mới phát hiện ra lỗi sai (chỗ QuickSort)
Đây là code của em nó(Accepted):

#include <stdio.h>
#include <stdlib.h>
const char *INP="MAX.INP";
const char *OUT="MAX.OUT";
int Maximum(int n);
void QuickSort(int a[],int l, int r);
void QuickSort(int a[],int l, int r)
{
int i,j,x,temp;
i=l;
j=r;
x=a[(l+r)/2];
do{
while(a*<x) i++;
while(a[j]>x) j--;
if(i<=j)
{
temp=a*;
a*=a[j];
a[j]=temp;
i++;
j--;
}
}while(i<=j);
if(l<j) QuickSort(a,l,j);
if(i<r) QuickSort(a,i,r);
}
int Maximum(int n)
{
int a[100000];
int i;
a[0]=0;
a[1]=1;
for(i=1;i<n/2+1;i++)
{
a[2*i]=a*;
a[2*i+1]=a*+a[i+1];
}
QuickSort(a,0,n);
return a[n];
}
void main()
{
int a[100000];
int i,n=0;
FILE *fi=fopen(INP,"r");
do
{
fscanf(fi,"%d",&a[n]);
if(a[n]<=0) break;
else n++;
}while(1);
fclose(fi);
FILE *fo=fopen(OUT,"w");
for(i=0;i<n;i++) fprintf(fi,"%d
",Maximum(a*));
fclose(fo);
}

08520059 · 20 Tháng Sáu 2011 18:32

Chúc mừng bạn trẻ. Có thể code ngắn hơn được không, bỏ phần QuickSort đi, tính Maximum 1 lần thôi.

10520180 · 20 Tháng Sáu 2011 20:10

nếu tìm max thì sẽ tốn thời gian hơn anh ah, nên dùng QuickSort nhanh hơn…em nghĩ zậy

07520004 · 20 Tháng Sáu 2011 20:15

[QUOTE=10520180;2199]nếu tìm max thì sẽ tốn thời gian hơn anh ah, nên dùng QuickSort nhanh hơn…em nghĩ zậy[/QUOTE]

quick sort độ phức tạp trung bình O(n*log(n)) trong khi tìm max luôn là O(n). Hình như khóa 5 học cấu trúc dữ liệu và giải thuật rồi mà phải không :-?

10520180 · 20 Tháng Sáu 2011 20:36

keke, cái đó em nghỉ hehe, mong các anh thông cảm,…

10520516 · 20 Tháng Sáu 2011 21:06

anh An đúng ùi…một vòng for thui… cần chi sắp…

08520059 · 20 Tháng Sáu 2011 21:16

[QUOTE=07520004;2201]quick sort độ phức tạp trung bình O(n*log(n)) trong khi tìm max luôn là O(n). Hình như khóa 5 học cấu trúc dữ liệu và giải thuật rồi mà phải không :-?[/QUOTE]

Bạn ý nói “…em nghĩ zậy” chắc là chưa học rồi. Hông bit bạn trẻ có hiểu ý mình ko ta. Dùng O(n) để duyệt dãy có hơi “cùi” nhưng hiệu quả (trong bài toán này).

10520516 · 20 Tháng Sáu 2011 21:28

à… các huynh ai có lời giải bài “Chia kẹo"hay “stone " mà không cần đệ quy và mãng đánh dấu… share em với… em làm bằng mãng đánh dấu …AC nhưng gần 2M ~~””!!

07520004 · 20 Tháng Sáu 2011 22:36

[QUOTE=10520516;2208]à… các huynh ai có lời giải bài “Chia kẹo"hay “stone " mà không cần đệ quy và mãng đánh dấu… share em với… em làm bằng mãng đánh dấu …AC nhưng gần 2M ~~””!![/QUOTE]

Post nó trong topic khác đi em, và chữ “mãng” chỉ xuất hiện trong từ “mãng xà” thôi em à

10520180 · 21 Tháng Sáu 2011 12:02

hồi còn học phổ thông thì mình có làm bài này nhưng sao giờ làm lại nó chạy không đúng, thôi ráng chờ nha bạn…

10520180 · 21 Tháng Sáu 2011 23:47

Mấy bác xem lại đoạn code sau của em nó sai chỗ nào mà em không biết được, em giải bài stone pile:http://acm.timus.ru/problem.aspx?space=1&num=1005:

#include <stdio.h>
#include <stdlib.h>
const char *INP="STONEPILE.INP";
const char *OUT="STONEPILE.OUT";
long a[105];
int d1[101*101],d2[101*101];
int n,m,sum=0;
void Enter();
void Process();
void Print();
void Enter()
{
int i;
FILE *fi=fopen(INP,"r");
fscanf(fi,"%d",&n);
for(i=1;i<=n;i++)
{
fscanf(fi,"%d",&a*);
sum=sum+a*;
}
m=sum/2;
fclose(fi);
}
void Process()
{
int i,j;
for(i=1;i<=101*101;i++) d1*=0,d2*=0,tr*=0;
d1[0]=1;
d2[0]=1;
for(i=1;i<=n;i++)
{
for(j=0;j<=sum-a*;i++)
if(d1*&&(d2[j+a*]==0) d2[j+a*]=1;
for(i=0;i<=101*101;i++) d1*=d2*;
}
}
void Print()
{
int i;
FILE *fo=fopen(OUT,"w");
while (d2[m]==0) m--;
fprintf(fo,"%d",sum-2*m);
fclose(fo);
}
void main()
{
Enter();
Process();
Print();
}

10520516 · 23 Tháng Sáu 2011 10:12

cũng là mảng thui… tốn bộ nhớ thôi rồi…
p/s hix mỗi lần gõ là chú ý tới “Mãng” hix

10520180 · 23 Tháng Sáu 2011 13:40

bạn có thể đưa code lên không??