1. Deskripsi topik
Ada larik a[1000] yang menyimpan 1000 bilangan bulat. Temukan semua pasangan bilangan dalam larik yang jumlahnya M. Misal arraynya -1,2,4,6,5,3,4,2,9,0,8,3, maka pasangan bilangan yang jumlahnya 8 adalah (-1,9), (2, 6), (4,4), (5,3), (5,3), (0,8).
2. Algoritma yang paling umum
Dalam kasus kompleksitas yang tidak dapat direduksi, algoritma paling sederhana untuk masalah ini adalah sebagai berikut:
Daftar statis pribadi<int[]> UseNormalWay(int[] arr, int sumTotal)
{
Daftar<int[]> hasil = Daftar baru<int[]>();
untuk (int i = 0; i < arr.Panjang; i++)
{
int ekspektasiNum = jumlahTotal - arr[i];
for (int j = i + 1; j < arr.Panjang; j++)
{
jika (arr[j] == angka harapan)
{
hasil.Tambahkan(new int[]{arr[i],expectNum});
}
}
}
hasil pengembalian;
}
Gunakan perulangan dua tingkat untuk menemukan semua pasangan yang jumlahnya merupakan jumlah total tetap, dan simpan pasangan yang ditemukan dalam Daftar. Namun, kompleksitas algoritma ini agak tinggi, dan sebenarnya melakukan beberapa pekerjaan berulang selama traversal:
1) Tidak perlu memproses urutan berpasangan sebelumnya pada loop berikutnya.
2) Saat mencari bilangan yang jumlahnya sumTotal, harus ada beberapa proses yang bisa digunakan bersama.
Berdasarkan dua poin ini, Anda dapat mengutip beberapa ide 01 knapsack atau pemrograman dinamis (mungkin tidak tepat, saya memiliki pemahaman yang dangkal tentang kedua ide ini) untuk meningkatkan algoritma ini dan menggunakan rekursi untuk beroperasi.
2. Gunakan algoritma rekursif
Kode yang menggunakan algoritma rekursif adalah sebagai berikut:
Daftar statis pribadi<int[]> UseRecursion(int[] arr, int panjang, int sumTotal)
{
Daftar<int[]> hasil = Daftar baru<int[]>();
int[] nextArr = int[panjang] baru;
int panjang berikutnya = 0;
int ekspektasiNum = jumlahTotal - arr[0];
int temukanStartNumCount = 0;
int temukanEndNumCount = 0;
untuk (int i = 1; i < panjang; i++)
{
jika (arr[i] == angka harapan)
{
int lingkaranCount = arr[0] == ekspektasiNum ? findEndNumCount : findStartNumCount;
jumlah lingkaran += 1;
untuk (int j = 0; j < jumlah lingkaran; j++)
{
hasil.Tambahkan(int baru[] { arr[0], ExpectNum });
}
temukanEndNumCount++;
}
lain jika (arr[i] == arr[0])
{
untuk (int j = 0; j < temukanEndNumCount; j++)
{
hasil.Tambahkan(new int[] {expectNum, arr[0] });
}
findStartNumCount++;
}
kalau tidak
{
nextArr[panjang berikutnya++] = arr[i];
}
}
jika (Panjang berikutnya > 0)
{
Daftar<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (int[] item di hasil berikutnya)
{
hasil.Tambahkan(item);
}
}
hasil pengembalian;
}
Setelah setiap rekursi, semua bilangan yang belum diperiksa kecocokannya dibentuk menjadi larik baru untuk diproses pada rekursi berikutnya, namun hal ini membuang banyak ruang, terutama jika lariknya besar, akan memakan banyak memori. . Agar tidak membuat array baru secara rekursif setiap saat, Anda dapat memprosesnya pada array asli, menghapus nomor yang cocok dari array, dan memindahkan nomor berikutnya ke depan untuk menggantikannya.
3. Algoritma perubahan dinamis array
Kode untuk algoritma ini adalah sebagai berikut:
Daftar statis pribadi<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
Daftar<int[]> hasil = Daftar baru<int[]>();
int startIndex = 0, endIndex = arr.Panjang - 1;
sementara (Indeks awal <Indeks akhir)
{
int ekspektasiNum = jumlahTotal - arr[startIndex];
int temukanStartNumCount = 0;
int temukanEndNumCount = 0;
untuk (int i = indeks awal + 1; i <= indeks akhir; i++)
{
jika (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
jika (arr[i] == angka harapan)
{
int lingkaranCount = arr[startIndex] == ekspektasiNum ? findEndNumCount : findStartNumCount;
jumlah lingkaran += 1;
untuk (int iStart = 0; iStart < jumlah lingkaran; iStart++)
{
hasil.Tambahkan(int baru[] { arr[startIndex], arr[i] });
}
temukanEndNumCount++;
indeks akhir--;
Saya--;
}
lain jika (arr[i] == arr[startIndex] && arr[startIndex] != ExpectNum)
{
untuk (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
hasil.Tambahkan(new int[] {expectNum, arr[i] });
}
findStartNumCount++;
indeks akhir--;
Saya--;
}
}
mulaiIndeks++;
}
hasil pengembalian;
}
Algoritma ini akan menghancurkan data dari array asli.
4. Perbandingan waktu ketiga algoritma
Meskipun tujuan awal dari dua algoritma terakhir adalah untuk mengurangi kompleksitas waktu, keduanya tidak jauh lebih baik daripada algoritma pertama dalam pengujian tertentu. Secara khusus, algoritma rekursif membutuhkan waktu yang jauh lebih lama daripada algoritma pertama. Mungkin ada masalah mendasar dengan ide saya, atau mungkin contoh ini terlalu sederhana dan membuat waktu yang dihabiskan oleh data seluler menjadi jelas.
Saya belum pernah melakukan banyak penelitian tentang algoritma. Saya harap para ahli dapat memberi saya beberapa saran.
5. Semua kode
kekosongan statis Utama (string[] args)
{
konstan ke dalam NUM_COUNT = 8000;
konstanta ke dalam MIN_NUM = -4;
konstanta ke dalam MAX_NUM = 12;
konstanta ke dalam TOTAL = 8;
int[] arr = HasilkanArray(NUM_COUNT, MIN_NUM, MAX_NUM);
//Console.WriteLine("Angka yang dihasilkan adalah:n------------------------------------ ---- -");
//PrintNumArray(arr);
//Cara biasa
Rentang Waktu normalTimeStart = Proses.GetCurrentProcess().TotalProcessorTime;
Stopwatch normalStw = Stopwatch baru();
normalStw.Mulai();
Daftar<int[]> hasilUseNormalWay = UseNormalWay(arr, TOTAL);
double normalCupTime = Proses.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMilliseconds;
normalStw.Berhenti();
double normalRealTime = normalStw.Elapsed.TotalMilliseconds;
// Cetak Hasil Normal
//Console.WriteLine("Hasil pasangan bilangan dengan cara biasa adalah:n-------------------------------- --");
//PrintNumPairs(hasilUseNormalWay);
// Cara rekursi
TimeSpan recuTimeStart = Proses.GetCurrentProcess().TotalProcessorTime;
Stopwatch recuStw = Stopwatch baru();
recuStw.Mulai();
Daftar<int[]> resultUseRecursionWay = UseRecursion(arr, arr.Length, TOTAL);
double recuCupTime = Proses.GetCurrentProcess().TotalProcessorTime.Subtract(recuTimeStart).TotalMilliseconds;
recuStw.Stop();
double recuRealTime = recuStw.Elapsed.TotalMilliseconds;
// Cetak Hasil Rekursi
//Console.WriteLine("Hasil pasangan bilangan dengan cara rekusi adalah:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);
// Cara tingkat lanjut
TimeSpan advTimeStart = Proses.GetCurrentProcess().TotalProcessorTime;
Stopwatch advStw = Stopwatch baru();
advStw.Mulai();
Daftar<int[]> hasilUseAdvancedWay = UseAdvancedWay(arr, TOTAL);
double advCupTime = Proses.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMilliseconds;
advStw.Stop();
double advRealTime = advStw.Elapsed.TotalMilliseconds;
// Cetak Hasil Lanjutan
//Console.WriteLine("Hasil pasangan bilangan dengan cara lanjutan adalah:n-------------------------------- --");
//PrintNumPairs(resultUseAdvancedWay);
Console.WriteLine("n==nWaktu yang digunakan:n---- -----------------------------------");
Console.WriteLine(String.Format("Normal : hitungan - {0} Waktu CPU - {1} Waktu Nyata - {2}", resultUseNormalWay.Count, normalCupTime, normalRealTime));
Console.WriteLine(String.Format("Rekursi: hitungan - {0} Waktu CPU - {1} Waktu Nyata - {2}", resultUseRecursionWay.Count, recuCupTime, recuRealTime));
Console.WriteLine(String.Format("Lanjutan : hitungan - {0} Waktu CPU - {1} Waktu Nyata - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));
Konsol.Baca();
}
int statis pribadi[] GenerateArray(int numCount, int minValue, int maxValue)
{
int[] arr = int baru[jumlahHitung];
Rdm acak = new Random((int)DateTime.Now.Ticks);
untuk (int i = 0; i < arr.Panjang; i++)
{
arr[i] = rdm.Berikutnya(nilaimin,nilaimaks);
}
kembali arr;
}
kekosongan statis pribadi PrintNumArray(int[] arr)
{
untuk (int i = 0; i < arr.Panjang; i++)
{
jika (saya > 0 && saya % 20 == 0)
{
Konsol.Tulis("n");
}
Console.Write(String.Format("{0,2} ", arr[i]));
}
Konsol.Tulis("n");
}
kekosongan statis pribadi PrintNumPairs(Daftar<int[]> numList)
{
untuk (int i = 0; i < numList.Count; i++)
{
jika (saya > 0 && saya % 10 == 0)
{
Konsol.Tulis("n");
}
Console.Write(string.Format("({0,2},{1,2}) ", numList[i][0], numList[i][1]));
}
Konsol.Tulis("n");
}
Daftar statis pribadi<int[]> UseNormalWay(int[] arr, int sumTotal)
{
Daftar<int[]> hasil = Daftar baru<int[]>();
untuk (int i = 0; i < arr.Panjang; i++)
{
int ekspektasiNum = jumlahTotal - arr[i];
for (int j = i + 1; j < arr.Panjang; j++)
{
jika (arr[j] == angka harapan)
{
hasil.Tambahkan(new int[]{arr[i],expectNum});
}
}
}
hasil pengembalian;
}
Daftar statis pribadi<int[]> UseRecursion(int[] arr, int panjang, int sumTotal)
{
Daftar<int[]> hasil = Daftar baru<int[]>();
int[] nextArr = int[panjang] baru;
int panjang berikutnya = 0;
int ekspektasiNum = jumlahTotal - arr[0];
int temukanStartNumCount = 0;
int temukanEndNumCount = 0;
untuk (int i = 1; i < panjang; i++)
{
jika (arr[i] == angka harapan)
{
int lingkaranCount = arr[0] == ekspektasiNum ? findEndNumCount : findStartNumCount;
jumlah lingkaran += 1;
untuk (int j = 0; j < jumlah lingkaran; j++)
{
hasil.Tambahkan(int baru[] { arr[0], ExpectNum });
}
temukanEndNumCount++;
}
lain jika (arr[i] == arr[0])
{
untuk (int j = 0; j < temukanEndNumCount; j++)
{
hasil.Tambahkan(new int[] {expectNum, arr[0] });
}
findStartNumCount++;
}
kalau tidak
{
nextArr[panjang berikutnya++] = arr[i];
}
}
jika (Panjang berikutnya > 0)
{
Daftar<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach (int[] item di hasil berikutnya)
{
hasil.Tambahkan(item);
}
}
hasil pengembalian;
}
Daftar statis pribadi<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
Daftar<int[]> hasil = Daftar baru<int[]>();
int startIndex = 0, endIndex = arr.Panjang - 1;
sementara (Indeks awal <Indeks akhir)
{
int ekspektasiNum = jumlahTotal - arr[startIndex];
int temukanStartNumCount = 0;
int temukanEndNumCount = 0;
untuk (int i = indeks awal + 1; i <= indeks akhir; i++)
{
jika (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
jika (arr[i] == angka harapan)
{
int lingkaranCount = arr[startIndex] == ekspektasiNum ? findEndNumCount : findStartNumCount;
jumlah lingkaran += 1;
untuk (int iStart = 0; iStart < jumlah lingkaran; iStart++)
{
hasil.Tambahkan(int baru[] { arr[startIndex], arr[i] });
}
temukanEndNumCount++;
indeks akhir--;
Saya--;
}
lain jika (arr[i] == arr[startIndex] && arr[startIndex] != ExpectNum)
{
untuk (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
hasil.Tambahkan(new int[] {expectNum, arr[i] });
}
findStartNumCount++;
indeks akhir--;
Saya--;
}
}
mulaiIndeks++;
}
hasil pengembalian;
}
-