Ai giúp em bài này đi ạ…… em cảm ơn nhiều nhiều ạ…
Một dãy con gồm các phần tử liên tiếp nhau trong một dãy cho trước được gọi
là đoạn. Cho dãy gồm N số tự nhiên, viết chương trình tìm đoạn ngắnnhất có tổng các
phần tử bằng giá trị K cho trước.
Input:Tập tin văn bản DOAN.INP
+ Dòng 1: chứa hai số tự nhiênN, K (1 <=N <=2000);
+ Các dòng tiếp theo: các phần tử của dãy, mỗi phần tử cách nhau một khoảng trắng.
Output:Tập tin văn bản DOAN.OUT, chứa một dòng duy nhất gồm hai số tự
nhiên x và b. Trong đó x: là chỉ số đầu đoạn; b: là số phần tử trong đoạn (chiều dài
đoạn). Nếu tìm không có (vô nghiệm) ghi 0 0.
Ví dụ:
DOAN.INP
16 11
4 5 7 6 10
3 6 2 8 12
4 0 0 7 1
1
DOAN.OUT
6 3
DOAN.INP
7 13
4 2
1
5 0
9 3
DOAN.OUT
0 0
Ai giúp em bài này đi ạ-.. em cảm ơn nhiều nhiều ạ… Một dãy con gồm các phần tử liên tiếp nhau trong một dãy cho trước được gọi là đoạn. Cho dãy
By Anna
Mình không biết bạn học ngôn ngữ nào nên mình đã code cả 2 ngôn ngữ là pascal và C++.
C++
#include<iostream>
#include<fstream>
using namespace std;
int main()
{
int k,n,a[100],tong,j,i,c=123456789,d=0;
cout<<“n=”; cin>>n;
cout<<“k=”; cin>>k;
for (i=1; i<=n; i++) {
cout<<“a[“<<i<<“]=”;cin>>a[i];
}
for ( i=1; i<=n; i++) {
j=i;
tong=a[i];
while (j<n && tong<=k && tong+a[j+1]<=k) {
j++;
tong+=a[j];
}
if (tong==k && j-i+1<=c-d+1){
d=i; c=j;
}
}
cout<<d<<” “; if (d != 0) cout<<c-d+1; else cout<<0;
return 0;
}
Pascal
uses crt;
var f:text; i,n,j,d,c,tong,k:longint; a:array[1..1000000]of longint;
begin
clrscr;
assign(f,’input.pas’);reset(f);
readln(f,n,k);
while not(eof(f)) do
begin
while not(eoln(f)) do begin inc(i); read(f,a[i]); end; readln(f);
end;
d:=0; c:=high(longint)-2;
close(f);
assign(f,’output.pas’);rewrite(f);
for i:=1 to n do
begin
j:=i;
tong:=a[i];
while (j<>n)and(tong<=k)and(tong+a[j+1]<=k) do begin inc(j); inc(tong,a[j]); end;
if (tong=k)and(j-i+1<c-d+1) then begin d:=i; c:=j; end;
end;
if d=0 then write(f,’0 0′)else write(f,d,’ ‘,c-d+1);
close(f);
end.
Nếu là dãy số không âm thì mình có cách làm như sau:
Biến start=0, end,s=0;
Cho end từ 0->n:
Giải thích:
Nếu s < k. Thì tất cả đoạn con [start,end] đều không thoã mãn.
Nếu s=k. Tìm thấy, tính cho lần sau.
Nếu s > k. Tất cả đoạn con bắt đầu từ start và sau end đều lớn hơn k nên không tính các đoan con từ start nữa. Chuyển sang đoạn bắt đầu từ start+1.
dpt O(n)