01/10/2018, 11:29
Số lần tráo đổi ít nhất để mảng có số chẵn lẻ luân phiên
mọi người cho e hỏi đoạn code này sao ko chạy đc vậy
ĐỀ BÀI : nhập vào 1 dãy n phần tử in ra số làm hoán vị ít nhất sao cho tạo ra dãy mà số chẵn ở vị trí chẵn
số lẻ ở vị trí lẻ
#include <stdio.h>
#include <conio.h>
#include <math.h>
//tạo 1 hàm hoán vị
void HoanVi(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
void ViTriChanLe(int a[], int n)
{
int dem = 0;
int sochan = 0, sole = 0;
// kiểm tra xem số lượng số chẵn có bằng số lượng số lẻ ko
for (int i = 0; i < n; i++)
{
if(a[i] % 2 == 0)
{
sochan ++;
}
else
{
sole ++;
}
}
if(abs(sochan - sole) >= 2 )// nếu không bằng tức ko thể có cách hoán vị nào thỏa --> xuất ra -1
{
printf("-1");
}
else// nếu = thì xử lý
{
for (int i = 0; i < n; i ++ )//duyệt hết mảng
{
if (abs(a[i] - i) % 2 == 0)//kiểm tra nếu xuất hiện phần tử chẵn ở vị trí lẻ hoặc lẻ ở vị trí chẵn
{
for (int j = i + 1; j < n; j++)// thì duyệt từ số sau đến hết mảng
{
if (abs(a[j] - a[j]) % 2 != 0)// nếu gặp phần tử đầu tiên khác tính chẵn lẻ
{
HoanVi(a[i], a[j]);// thì hoán vị 2 phần tử đó
dem++;// tăng số lần hoán vị lên 1
printf("%4d%4d", i+1, j+1);// in ra các vị trí hoán vị (tính từ 1)
}
break; // thoát ngay không duyệt tiếp nữa
}
}
}
printf("so lan hoan vi it nhat la : %d",dem);// in ra số lần hoán vị
}
}
int main()
{
int a[6] = { 1,3,5,4,6,2 };
int n = 6;
ViTriChanLe(a, n);
_getch();
return 0;
}
Bài liên quan
Bạn đã chạy code trên máy chưa? Code có bị báo lỗi gì không? Console hiện lên cái gì? Nếu có thì up lên, chứ up mỗi code chỏng chơ lên thì chẳng ai giúp được gì.
Chào vuong2k!
Trong C không có định nghĩa tham chiếu nha bạn!
void HoanVi(int &x, int &y)Đây là link có thể bạn giúp bạn: http://vncoding.net/2016/02/16/truyen-tham-tri-va-tham-bien-cho-ham
:v e code c++ bằng cú pháp cảu c trên visual nên nó có dùng tham chiếu
kiểm thử thì code e chạy tốt nhưng nó ra :
SO LAN XUAT HIEN IT NHAT LA : 0
Thực sự mình nghi ngờ cái giải thuật này lắm, nhất là khẳng định “nhỏ nhất”.
ok nếu vậy thì mốt bạn nhớ tag đúng trang nha! C++ chứ không phải C chứ về sau có nhiều người nhìn nhầm!
Test case của bạn thì mình không biết. nhưng xét chung thì thuật toán này của bạn sẽ có vấn đề nhé
a có thể chỉ giúp e vấn đề ở đâu đc ko ạ
Bạn tự đọc lại dòng này xem.
Vả lại, nếu số chẵn ở vị trí chẵn, số lẻ ở vị trí lẻ thì
Cho nên thuật toán của bạn sai chắc, bởi điều kiện swap a[i], a[j] quá yếu.
sao lại luôn đúng đc : gs a[0] = 1 (tức 1 ở vị trí 1 )
Kể cả như vậy, nhưng thuật toán của bạn vẫn sai.
Thuật toán này có một số điểm sau:
Bạn chưa nói rõ là vị trí bắt đầu từ 0 hay 1.
Bạn không để ý trường hợp n lẻ à?
có đáp số. Thế mà bạn cho là vô nghiệm luôn.
Phần include thư viện của c bạn đã sửa lại chưa, ko sao mà tham chiếu nhỉ
Permutations: any implementation of the Cayley distance?
Bạn mod 2 hết rồi tính khoảng cách Cayley với “101010…”.
Bước đầu tiên là encode nó ntn: http://www.cnblogs.com/grandyang/p/6366738.html
sau đó phân giải nó https://spellscroll.wordpress.com/2008/12/19/permutation-cycle-decomposition/
có vẻ bạn sai chỗ này
if (abs(a[j] - a[j]) % 2 != 0)
KQ: 0 % 2 = 0; nên vòng đó ko chạy.