Xin chỉ giáo =.= (bài tập TKTT)

19. Cho một xâu S (độ dài không quá 200) chỉ gồm ba kí tự ‘A’, ‘B’ và ‘C’. Ta có
phép đổi chỗ hai kí tự bất kỳ trong xâu. Hãy tìm cách biến đổi ít bước nhất để
được xâu theo thứ tự tăng dần.
Nếu dùng nhánh cận để làm thì cũng được nhưng lằng nhằng quá, độ phức tạp cao ...

Em làm như sau: .. ko biết được gọi là thuật toán tham ko :p
note: Bước 1 xác định xâu out put

Trời đề của e có 2 dòng nhưng đọc vẫn chưa hiểu hết ý.pác nào nhanh trí giúp e phát.E làm 1 mình nên chẳng có thằng mèo nào để hỏi cả...


20. Cho N (N≤1000) đoạn số [ai, bi], hãy chọn một tập hợp gồm ít số nhất mà mỗi đoạn số nguyên trên đều có ít nhất 2 số trong tập đó.

ai xem ho bai 12 voi chuoi ca nai

Uhm, Bài của Đạt thử sử dụng chia để trị xem. Cụ thể là thuật toán tìm kiếm nhị phân đó. Để tui thử xem rùi post lên nha

các pác cho ý kiến bài của e cái,khó wa..


20. Cho N (N≤1000) đoạn số [ai, bi], hãy chọn một tập hợp gồm ít số nhất mà mỗi đoạn số nguyên trên đều có ít nhất 2 số trong tập đó.

Bài 17: Có 16 đồng xu xếp thành bảng 4x4, mỗi
đồng xu có thể úp hoặc ngửa. Tại mỗi bước ta có phép biến đổi sau: chọn một đồng
xu và thay đổi trạng thái của đồng xu đó và tất cả các đồng xu nằm ở ô chung cạnh
(úp thành ngửa, ngửa thành úp). Cho trước trạng thái các đồng xu, hãy lập trình
tìm số phép biến đổi ít nhất để đưa về trạng thái tất cả các đồng xu hoặc đều
úp hoặc đều ngửa.
Hichic, em chả hình thành đc tí j về phương pháp giải bài này cả Học xong cả kỳ rùi mà có kảm giác như mình chưa biết cái j cả.

riêng bài của hạnh thì một là dùng thuật toán AKT hay AT đều có thể giải quyết được. Nếu như mình hiểu không nhầm thì đại loại ý của bài toán là thế này nó gần giống với bài cờ vua: cho trước bàn cơ nguồn mà các ô được sắp không theo thứ tự cái cần làm là sắp bàn cờ lại theo thứ tự cho yêu cầu mà số bước đổi chỗ quân cờ là ít nhất. Hạnh thử xem coi nếu không phải thì đành phải đợi bác nào biết post bài giúp vậy thui :(

ờ! t sẽ cố gắng xem lại bài và hỉu. hì hì. thank ông cái. ko biết nút thanks nó nằm chỗ nào ấy nhỉ

Moi nguoi oi! Moi nguoi chi giao giup to bai 18 voi! To xin da ta! da ta! da ta!

ai xem ho t bai 32 voi. dung thuat toan gi day/ huhu,chet rui,ko bit lam bai.hix

Các pác góp ý bài e cái,e mới có cái ý tưởng.....

20. Cho N (N≤1000) đoạn số [ai, bi], hãy chọn một tập hợp gồm ít số nhất mà mỗi đoạn số nguyên trên đều có ít nhất 2 số trong tập đó.


+Bươc1:Duyệt đoạn đầu tiên,tìm 2 ptu thuộc đoạn đang duyệt có số lần xuất hiện trong tất cả các đoạn nhiều nhất.Đẩy 2 ptu này vào tập hợp T.

+Bước2:Duyệt tiếp đến các đoạn tiếp theo.

-TH1:Nếu đoạn đang xét không có ptu nào trùng với ptu của tập T thì làm như bước 1.

-Th2:Đoạn đang xét có 1 ptu đã có trong T.Ta tìm 1 phần tử trong các ptu còn lại có số lần xuất hiện trong tất cả các đoạn nhiều nhất và đẩy vào T.

-TH3:Đoạn đang xét có >=2 ptu đã có trong T.Ta không cần duyệt đoạn này nữa mà chuyển sang đoạn tiếp.

Cứ làm như thế cho đến khi duyệt hết các đoạn con số nguyên và ta được tâp T cần tìm….

Hỡi các cao thủ A3 co ai rỗi thì viết hộ thuật giải bài 12 với

"hỡi đồng bào tôi nói đồng bào có nghe rõ không" trích lời chủ tịch Hồ Chí Minh

đây là ý tưởng bài 37, hỡi đồng bào xem giúp phát.

tớ dùng phương pháp tham lam:

Ban đầu duyệt toàn mảng n x n( 2 vòng lặp for), tìm ô có giá trị lớn nhất. ghi giá trị đó, cộng vào tổng sum, đánh dấu hàng và cột chứa ô đó( bằng cách gán giá trị các ô thuộc hàng hoặc cột đó bằng -1)

Sau đó, duyệt toàn mảng( 2 vòng lặp for), tìm tiếp giá trị lớn nhất trong các ô còn lại (sau khi đánh dấu hàng và cột đã có ô được chọn). ghi giá trị đó, cộng vào tổng sum, đánh dấu hàng và cột chứa ô đó

trong mỗi lần chọn được ô, ta dùng một biến đếm đếm sô ô đã được chọn

Quá trình chọn trên dừng lại khi biến đếm bằng k.

ghi ra k số được chọn(giá trị, vị trí = một mảng cấu trúc lưu các ô đó) ghi ra tổng max của k sô đó

- độ phức tạp thuật toán là: n*n*k = O(n^3)

hỡi đồng bào xem hộ phát

Thuật toán trên ko đúng !
Vì nếu tại ô (i,j) ta chọn dc 1 số now-max
in matrix, khi đó ta coi như xóa bỏ hàng i và cột j, tức là xóa toàn bộ
các ô (i,k) & (l,j) -> có thể xóa mất 1 số ô lớn gần nhất matrix
(chỉ xếp sau max hiện tại)
như vậy các số tiếp theo mà bạn chọn sẽ ko tối tưu.(chỉ tối ưu giá trị hiện tại chứ ko phải là toàn bộ K số )

QHD dc đó ! nghĩ thử coi ! O(n2) thui
VD cho matrix sau :

1 2 3
8 11 9
1 7 1

b1: bạn chọn 11.
b2: bạn chon 3
Sum = 14.

nhưng pán tối ưu của bài toán phải là 9,7 =>Sum = 16

hoho luc dau minh bai 19 gio chay sang bai 22 van cha biet lam
cac cao thu giup minh vathanh voi

Mong các pác gợi ý em thuật toán bài 36 :

Phân trang


Văn bản là một dãy gồm N từ đánh số từ 1 đến N.
Từ i có độ dài là w_i (i=1..N). Phân trang là một
cáh xếp lần lượt các từ của văn bản vào các dòng, mỗi dòng có đội dài L, sao cho tổng đội dài của cá từ trên
cùng một dòng không vượt quá L. Ta gọi
hệ số phạt của mỗi dòng trong cách phân trang là hiệu số L-S, trong đó S là tổng độ dài của cá từ xếp trên dòng
đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt
của các dòng.
Tìm cách phân trang với hệ số phạt nhỏ nhất.
Pác nào rỗi thì làm hộ em cái Code C dc ko?
Xin chân thành cảm ơn!!

xem ho mik bai 33 nhe'

anh long gay(LE THANH LONG) ANH LAM BAI 3 DUNG KHONG LAM CUNG THI LIEN HE VOI EM BACH DAY PHONE 0983718838

Bach da em sao bai day kho vay ma may cung fai nho ah!!!
Tu lam di chu neu ko lam dc thi nop bai ko giong tao chu
may lo bo anh em vay ah:))

VoTienKhoangHau đã viết:

Thuật toán trên ko đúng !
Vì nếu tại ô (i,j) ta chọn dc 1 số now-max
in matrix, khi đó ta coi như xóa bỏ hàng i và cột j, tức là xóa toàn bộ
các ô (i,k) & (l,j) -> có thể xóa mất 1 số ô lớn gần nhất matrix
(chỉ xếp sau max hiện tại)
như vậy các số tiếp theo mà bạn chọn sẽ ko tối tưu.(chỉ tối ưu giá trị hiện tại chứ ko phải là toàn bộ K số )

QHD dc đó ! nghĩ thử coi ! O(n2) thui
VD cho matrix sau :

1 2 3
8 11 9
1 7 1

b1: bạn chọn 11.
b2: bạn chon 3
Sum = 14.

nhưng pán tối ưu của bài toán phải là 9,7 =>Sum = 16

hì hì, cảm ơn nha, sao bạn không giúp mình phát, không cần hết đâu chỉ cần giúp mình tìm công thức truy hôi và cách làm truy vêt. còn lại tớ sẽ thêm mắm thêm muối vào,. tớ nghĩ mãi mà chả bit làm.
cảm ơn trược nha.

Bài này ai có cách giải không (Bài 16)





16. Một lưới MxN (M, N ≤ 10) ô, mỗi ô đặt một
bóng đèn bật hoặc tắt. Trên mỗi dòng và mỗi cột có một công tắc. Nếu tác động
vào công tắc dòng i (i=1..M)
hoặc công tắc cột j (j=1..N) thì tất cả các bóng đèn trên dòng i hoặc cột j sẽ thay đổi trạng thái. Hãy tìm cách tác động vào các công tắc để
được nhiều đèn sáng nhất.

Trích dẫn :

Bài này ai có cách giải không (Bài 16)
16. Một lưới MxN (M, N ≤ 10) ô, mỗi ô đặt một
bóng đèn bật hoặc tắt. Trên mỗi dòng và mỗi cột có một công tắc. Nếu tác động
vào công tắc dòng i (i=1..M)
hoặc công tắc cột j (j=1..N) thì tất cả các bóng đèn trên dòng i hoặc cột j sẽ thay đổi trạng thái. Hãy tìm cách tác động vào các công tắc để
được nhiều đèn sáng nhất.

Bài này lần đầu là bài của mình nên mình cũng nghĩ 1 chút rùi.thuật toán này k bít có đúng k nhé.
-Giả sử 0 là trạng thái bóng đèn [i,j] tắt,1 là sáng.
-Đếm số bóng đèn sáng của từng cột rùi xếp chúng vào 1 mảng giảm dần theo số bóng sáng.Hàng cũng làm thế.
-Trường hợp 1:tác động lên hàng.
-Xét cột j có số bóng sáng nhiều nhất.
+Cho giao với hàng i có số bóng sáng ít nhất(vì khi bật nó sẽ sáng nhiều nhất).Nếu bóng giao giữa cột và hàng[i,j] là bóng tắt thì tác động vào hàng này sẽ đc kết quả max cần tìm(tối ưu nhất).Nếu bóng đó là bóng sáng thì ta phải xét đến hàng có số bóng sáng ít hơn hàng max 1 bóng(nếu không có hàng nào như thế thì lấy lun trường hợp vừa xét là kết quả).Nếu bóng giao là tắt thì khi tác động vào hàng này ta sẽ có số bóng sáng max và chính bằng trường hợp 2 khi xét hàng i và sẽ có 2 cách tác động(tối ưu thứ 2).ngoài ra ta k phải xét các TH hàng khac vì có xét thì cũng k đc số bóng sáng nhiều hơn 2 cách trên.
-Xét hàng cũng tương tự.

Bài 35: ai giải được thì tuyệt quá. Ân nhân của bạn Hà Thị Thanh Vân





35. Least-Squares Segmentation:


Ta định nghĩa trọng số của đoạn số từ số ở vị
trí i đến vị trí thứ j của dãy số nguyên a[1], a[2] ...a[N] là: ∑ _k=i..j (a[k]-mean)² trong đó mean= (∑ _k=i..j
a[k])/(j-i+1).


Hãy chia dãy số A thành G đoạn (1< G²<N) để tổng trọng số của các đoạn là nhỏ nhất.

anh em chỉ giáo cho tớ bài 22 cái :








ĐỀ BÀI :
Cho một số nguyên N. Hãy tìm
cách phân tích số N thành các số nguyên dương p₁, p₂,
... p_k sao cho:


- p₁,
p₂, ... p_k: đôi một khác nhau


- p₁
+ p₂ + ... + p_k
= N


- S = p₁*
p₂ * ...* p_k đạtgiá trị lớn
nhất.


Tớ nghĩ là dùng nhánh cận cho k chay từ 1 tới N rồi tính tích.
các cao thủ chỉ giáo cái xin đa tạ

he. Bài 22 phải hỏi Hoàng Chí Thành. Tổ hợp là tuyệt chiêu của Mr.

Bài 22 giống bài phân tích số đó. Dùng nhánh cận. Anh tìm trên mạng bài toán phân tích số đó. Sau mỗi bước tìm được kết quả thì mình so sánh với kết quá trước đó.

theo như ý của cường mình đã tim dc bài phân tích số N và đếm số phân tích.mọi người giúp mình phần duyệt nhánh cận cái. đây là code bài đó



/****************************************************************************+ Cho so nguyen duong N.
+ Dem so cach phan tich so N thanh tong cac so nguyen duong. ****************************************************************************/ #include<stdio.h>
#include<conio.h>

int main()
{
unsigned long f[1000]; // f[m,v]: phan tich so V thanh tong cac so nguyen duong <=m
int v,m,n,i;
printf("Nhap so nguyen duong n= ");
scanf("%ld",&n);
while(n<0)
{
printf("Nhap so nguyen duong n= ");
scanf("%ld",&n);
}
for(i=0;i<=n;i++)
f[i]=0;
f[0]=1;
for(m=1;m<=n;m++)
for(v=m;v<=n;v++)
f[v]=f[v]+f[v-m];
printf("Co %ld cach phan tich.\n",f[n]);
getch();
return 0;
}

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

int sum_a=0 ,sum_b=0, list[200] ;
int truyvet[200][200];
char s[200],so[200];

int read_input() //Hàm đọc file input
{
FILE *f;
f=fopen("Input.txt","r");
fscanf(f,"%[^\n]\n",s);
printf("Xau Input:\n%s\n",s);
fclose(f);
return strlen(s);
}

void xacdinh_output(int n) //Hàm xác đinh xâu đích
{
int i,j;
for (i=0;i<n;i++)
{
if(s[i]=='a') sum_a++;
if(s[i]=='b') sum_b++;
}
for (i=0;i<sum_a;i++)
so[i]='a';
for (i=sum_a;i<sum_a+sum_b;i++)
so[i]='b';
for (i=sum_a+sum_b;i<n;i++)
so[i]='c';
}

void sap_xep(int n) //Hàm xắp xếp bằng cách đổi chỗ dùng thuật toán tham
{
int i,j;
for (i=0;i<n;i++)
list[i] = 0;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
truyvet[i][j] = 0;
for (i=0;i<n;i++)
if (s[i]==so[i]||list[i]==1)
list[i] = 1; ////Loại những kí tự đã đứng đúng vị trí ra khỏi danh sách tìm kiếm
else
for (j=n-1;j>i;j--) //Tìm những cặp chỉ cần đổi chỗ 1 lần là có đúng vị trí
if (s[i]==so[j] && s[j]==so[i] && list[j]==0)
{
list[i] = 1; list[j] = 1; truyvet[i][j]=1;
j=i; //Thoát vòng for
}

for (i=0;i<n-1;i++) //Đưa các ký tự a về đúng chỗ của nó
if (list[i]==0 && s[i]!='a')
for (j=i+1;j<n;j++)
if (s[j]=='a'&& list[j]==0)
{
list[i] = 1; list[j] = 2; truyvet[i][j]=1;
j=n;
}
for (i=n-1;i>sum_a-1;i--) //Đưa các ký tự b,c về đúng vị trí
if (list[i]<1)
for (j=sum_a;j<n;j++)
if (list[j]==2)
{
list[j]=1; truyvet[i][j]=1;
j=n;
}
}




void truy_vet(int n) //Hàm truy vết
{
int count=0,i,j; //biến đếm số lần biến đổi xâu
for (i=0;i<n;i++)
for (j=0;j<n;j++)
{
if (truyvet[i][j]==1)
{
printf("Doi cho cap vi tri %d va %d\n",i,j);
so[n]=s[i]; //Đổi chỗ hai vị trí i và j
s[i]=s[j];
s[j]=so[n];
printf("%s\n",s); //In ra kết quả sau khi đổi chỗ cặp i,j
count++;
}
}
printf("can it nhat %d lan bien doi",count);
}

int main()
{
int n;
n=read_input();
xacdinh_output(n);
sap_xep(n);
truy_vet(n);
getch();
}

Input là xâu s: gồm các kí tự a,b,c có độ dài <200
Ví dụ :
acbacabacabcabacabacabcabacabacaacabacaacaacabacabcaacaac
Bài của em đó ... ko theo thuật toán nào cả huhuhu

ek. Bài phân tích số anh dùng quy hoạch động à. Thế thì kết quả chỉ ra số cách phân tích thôi chứ không ra từng kết quả cụ thể. Thế thì làm sao duyệt nhánh cận được. Tìm lại đi. Trong sách của Lê Minh Hoàng có đó. Code cũng ngắn mà. Dùng đệ quy mới có thể liệt kê tất cả các trường hợp được