Bahasa :
SWEWE Anggota :Login |Pendaftaran
Cari
Masyarakat ensiklopedia |Ensiklopedia Jawaban |Kirim pertanyaan |Pengetahuan kosakata |Upload pengetahuan
Sebelumnya 1 Berikutnya Pilih Halaman

Pasangan membalikkan

Definisi

Untuk array N bilangan bulat non-negatif A [1 .. n], jika saya <j, dan A [i]> A [j], disebut (A [i], A [j]) array A dalam sepasang terbalik.

Misalnya, array (3,1,4,5,2) di balik ada (3,1), (3,2), (4,2), (5,2), total empat.

Jumlah memecahkan masalah pada sebaliknya

Deskripsi masalah

Mengingat sebuah array, cari array berisi jumlah yang tepat terbalik.

Metode pemecahanMetode Satu: metode yang paling primitif, menggunakan pencacahan loop ganda. Kompleksitas waktu dari algoritma ini adalah O (n ^ 2).

C kode adalah sebagai berikut:

int count_inversion (int * a, int N)

{

int count = 0;

int i, j;

untuk (i = 0; i <N, i )

for (j = i 1; j <N, j )

if (a [i]> a [j])

count ;

kembali menghitung;

}

Kode Pascal adalah sebagai berikut:

var i, j, k, n: longint;

a: array [1 .. 1000000] of longint;

mulai

readln (n);

untuk i: = 1 sampai n lakukan membaca (a [i]);

k: = 0;

untuk i: = 1 sampai n-1 lakukan

untuk j: = i 1 sampai n lakukan

jika [i]> a [j] maka inc (k);

writeln (k);


Sebelumnya 1 Berikutnya Pilih Halaman
Pemakai Ulasan
Belum ada komentar
Saya ingin komentar [Pengunjung (54.226.*.*) | Login ]

Bahasa :
| Periksa kode :


Cari

版权申明 | 隐私权政策 | Hak cipta @2018 Dunia pengetahuan ensiklopedis