Oʻzbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi mirzo ulug‘bek nomidagi milliy universitetininig jizzax filiali

OʻZBEKISTON RESPUBLIKASI OLIY TA’LIM, FAN VA INNOVATSIYALAR VAZIRLIGI

MIRZO ULUG‘BEK NOMIDAGI MILLIY UNIVERSITETININIG JIZZAX FILIALI

AMALIY MATEMATIKA FAKULTETI

«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» kafedrasi

“ALGORITMLAR VA BERILGANLAR STRUKTURASI” FANIDAN

3-MUSTAQIL ISHI

Bajardi: “Axborot tizimlari va texnologiyalari” yoʻnalishi

2-kurs 21-21 guruh talabasi Rahmonov Salohiddin
Tekshirdi: Tojiyev Ma’ruf

Jizzax – 2023
Rahmonov Salohiddin. 18-variant

Variant	M1	M2	M3	M4
18	18	12	7	13

1-Mavzu: Satrdagi barcha palindromalarni toppish algoritmi
7-variant
Reja:

1. 
   Satrdagi barcha palindromalarni topish algoritmi.
   
2. 
   Satrdagi barcha palindromalarni topish algoritmi C#dasturi.
   
3. 
   Foydalanilgan adabiyotlar
   
4. 
   Xulosa.
   

Berilgan qatorning barcha aniq palindromik pastki qatorlarini toping.

Kichik ASCII belgilar qatorini hisobga olib, uning barcha aniq uzluksiz palindromik pastki qatorlarini toping.
Misollar:
Kirish: str = "abaaa"
Chiqish: Quyida 5 ta palindrom pastki qatorlari mavjud
a
aa
aaa
aba
b
Kirish: str = "geek"
Chiqish: Quyida 4 ta palindrom pastki qatorlari mavjud
e
ee
g
k
Tavsiya etilgan amaliyot
Aniq palindromik pastki qatorlar
1-usul:
1-qadam: O‘zgartirilgan Manacher algoritmi yordamida barcha palindrom -larni topish:
Har bir belgini aylanma sifatida ko‘rib, ko‘rib chiqilayotgan pivot belgisida joylashgan juft va toq uzunlikdagi palindromlarning uzunligini topish uchun ikkala tomonni kengaytiring va uzunlikni 2 massivda (toq) saqlang. & hatto).
Bu bosqich uchun vaqt murakkabligi O(n^2)
2-qadam: HashMap-ga barcha topilgan palindromlarni kiritish:
Oldingi bosqichda topilgan barcha palindromlarni HashMap-ga kiriting. Shuningdek, satrdagi barcha individual belgilarni HashMap-ga kiriting (aniq bir harfli palindromik pastki qatorlarni yaratish uchun).
Ushbu bosqichning vaqt murakkabligi O(n^3) ga teng, chunki xeshni qo'shish qidiruvi O(1) vaqtni oladi. E'tibor bering, satrning ko'pi bilan O(n^2) palindrom pastki qatorlari bo'lishi mumkin. Quyidagi C++ kodida tartiblangan xashmap qo'llaniladi, bu erda kiritish va qidirishning vaqt murakkabligi O (Logn). C++ da buyurtma qilingan xashmap Red Black Tree yordamida amalga oshiriladi .
3-qadam: Aniq palindromlarni va bunday aniq palindromlar sonini chop etish:
Oxirgi qadam HashMap-da saqlangan barcha qiymatlarni chop etishdir (Faqat alohida elementlar HashMap xususiyati tufayli xeshlanadi). Xaritaning o'lchami aniq palindromik uzluksiz pastki qatorlar sonini beradi.
Quyida yuqoridagi fikrni amalga oshirish ko'rsatilgan.
// C# program to find all distinct palindrome
// sub-strings of a given string
using System;
using System.Collections.Generic;
class GFG
{
// Function to print all distinct palindrome
// sub-strings of s
public static void palindromeSubStrs(string s)
{
//map m;
Dictionary < string,
int > m = new Dictionary < string,
int > ();
int n = s.Length;
// table for storing results (2 rows for odd-
// and even-length palindromes
int[, ] R = new int[2, n + 1];
// Find all sub-string palindromes from the
// given input string insert 'guards' to
// iterate easily over s
s = "@" + s + "#";
for (int j = 0; j <= 1; j++)
{
int rp = 0; // length of 'palindrome radius'
R[j, 0] = 0;
int i = 1;
while (i <= n)
{
// Attempt to expand palindrome centered
// at i
while (s[i - rp - 1] == s[i + j + rp])
// Incrementing the length of
// palindromic radius as and
// when we find valid palindrome
rp++;
// Assigning the found palindromic length
// to odd/even length array
R[j, i] = rp;
int k = 1;
while ((R[j, i - k] != rp - k) && k < rp)
{
R[j, i + k] = Math.Min(R[j, i - k], rp - k);
k++;
}
rp = Math.Max(rp - k, 0);
i += k;
}
}
// remove 'guards'
s = s.Substring(1);
// Put all obtained palindromes in a hash map to
// find only distinct palindromess
if (!m.ContainsKey(s.Substring(0, 1)))
m.Add(s.Substring(0, 1), 1);
else
m[s.Substring(0, 1)]++;
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= 1; j++)
for (int rp = R[j, i]; rp > 0; rp--)
{
if (!m.ContainsKey(s.Substring(i - rp - 1, 2 * rp + j)))
m.Add(s.Substring(i - rp - 1, 2 * rp + j), 1);
else
m[s.Substring(i - rp - 1, 2 * rp + j)]++;
}
if (!m.ContainsKey(s.Substring(i, 1)))
m.Add(s.Substring(i, 1), 1);
else
m[s.Substring(i, 1)]++;
}
// printing all distinct palindromes from
// hash map
Console.WriteLine("Below are " + (m.Count));
foreach(KeyValuePair < string, int > ii in m)
Console.WriteLine(ii.Key);
}
// Driver Code
public static void Main(string[] args)
{
palindromeSubStrs("abaaa");
}
} // This code is contributed by
using System;
class GFG
{
static int solve(string s)
{
int n = s.Length;
// dp array to store whether a substring is palindrome
// or not using dynamic programming we can solve this
// in O(N^2)
// dp[i][j] will be true (1) if substring (i, j) is
// palindrome else false (0)
bool[][] dp = new bool[n][];
for (int i = 0; i < n; i++)
{
dp[i] = new bool[n];
// base case every char is palindrome
dp[i][i] = true;
// check for every substring of length 2
if (i < n - 1 && s[i] == s[i + 1])
{
dp[i][i + 1] = true;
}
}
// check every substring of length greater than 2 for
// palindrome
for (int len = 3; len <= n; len++)
{
for (int i = 0; i + len - 1 < n; i++)
{
if (s[i] == s[i + len - 1] && dp[i + 1][i + len - 2])
{
dp[i][i + len - 1] = true;
}
}
}
// here we will apply kmp algorithm for substrings
// starting from i = 0 to n-1 when we will find prefix
// and suffix of a substring to be equal and it is
// palindrome we will make dp[i][j] for that suffix to be
// false which means it is already added in the prefix
// and we should not count it anymore.
int[] kmp = new int[n];
for (int i = 0; i < n; i++)
{
// starting kmp for every i from 0 to n-1
int j = 0, k = 1;
while (k + i < n)
{
if (s[j + i] == s[k + i])
{
// make suffix to be false
// if this suffix is palindrome then it is
// already included in prefix
dp[k + i - j][k + i] = false;
kmp[k++] = ++j;
}
else if (j > 0)
{
j = kmp[j - 1];
}
else
{
kmp[k++] = 0;
}
}
}
int count = 0;
for (int i = 0; i < n; i++)
{
string str = "";
for (int j = i; j < n; j++)
{
str += s[j];
if (dp[i][j])
{
// count number of resultant distinct
// substrings and print that substring
count++;
Console.WriteLine(str);
} } }
Console.WriteLine("Total number of distinct palindromes is "+ count);
return count;
}
// Driver code starts
static void Main(string[] args)
{
string s1 = "abaaa";
string s2 = "aaaaaaaaaa";
solve(s1);
solve(s2);
}
// Driver code ends
} // This code is contributed by imruhrbf8.
Chiqish
a
aba
b
aa
aaa
Turli palindromlarning umumiy soni 5 ta
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
Turli palindromlarning umumiy soni 10 ta
C# da Palindrome dasturi
Qaytish: C#.NET Dasturlari va Algoritmlari
Misollar bilan C# tilida Palindrom dasturi (Raqam va satr).
Ushbu maqolada men C# tilidagi Palindrom dasturini (Palindrom soni va palindrom satri) misollar bilan muhokama qilmoqchiman . Iltimos, avvalgi maqolamizni o'qing, unda biz C# tilidagi Prime Number dasturini misollar bilan muhokama qildik. Bu berilgan raqam yoki satr palindrom yoki yo'qligini tekshirish uchun mantiqni yozish uchun intervyuda berilgan intervyu savollaridan biridir. Ushbu maqolaning bir qismi sifatida biz quyidagi ko'rsatmalarni muhokama qilamiz.
Palindrom raqami:
Palindrom soni - bu raqamning raqamlarini teskarisiga aylantirgandan keyin bir xil bo'ladigan raqam. Masalan, 121, 232, 12344321, 34543, 98789 kabi sonlar palindrom sonlaridir.
Berilgan raqam Palindrom yoki C# da emasligini qanday tekshirish mumkin?
C# da Palindrom raqamini tekshirish algoritmi:
Birinchidan, tekshirmoqchi bo'lgan foydalanuvchidan raqamni oling
Ushbu raqamni vaqtinchalik o'zgaruvchida saqlang.Bu raqamni teskari aylantiring.Vaqtinchalik raqamni teskari raqam bilan solishtiring.Agar ikkala raqam bir xil bo'lsa, u holda chop eting palindrom raqami, aks holda chop eting, bu palindrom raqami emas.
Misol: C# da Palindrom raqamlari dasturi
Quyidagi C# dasturi foydalanuvchiga raqam kiritish imkonini beradi va keyin bu raqam Palindrom raqami yoki yo'qligini tekshiradi.
using System;
namespace LogicalPrograms
{
public class Program
{
static void Main(string[] args)
{
Console.Write("Enter a Number To Check Palindrome : ");
int number = int.Parse(Console.ReadLine());
int remineder, sum = 0;
int temp = number;
while (number > 0)
{
//Get the remainder by dividing the number with 10
remineder = number % 10;
//multiply the sum with 10 and then add the remainder
sum = (sum * 10) + remineder;
//Get the quotient by dividing the number with 10
number = number / 10;
}
if (temp == sum)
{
Console.WriteLine($"Number {temp} is Palindrome.");
}
else
{
Console.WriteLine($"Number {temp} is not Palindrome");
}
Console.ReadKey();
}
}
}
Chiqish:
Berilgan raqam Palindrom yoki yo'qligini qanday tekshirish mumkin.
Berilgan satr Palindrom yoki C# da emasligini qanday tekshirish mumkin.
Keyingi dasturda konsoldan kirish sifatida satrni olamiz. Keyin for loop yordamida satrni teskari o'zgartiramiz va teskari satr qiymatini teskari o'zgaruvchida saqlaymiz. Nihoyat, biz asl va teskari qiymatlar bir xil yoki yo'qligini tekshiramiz. Agar ikkalasi bir xil bo'lsa, satr Palindrom, aks holda u Palindrom emas.
using System;
namespace LogicalPrograms
{
public class Program
{
static void Main(string[] args)
{
Console.Write("Enter a string to Check Palindrome : ");
string name = Console.ReadLine();
string reverse = string.Empty;
for (int i = name.Length - 1; i >= 0; i--)
{
reverse += name[i];
}
if (name == reverse)
{
Console.WriteLine($"{name} is Palindrome.");
}
else
{
Console.WriteLine($"{name} is not Palindrome");
}
Console.ReadKey();
}
}
}
Chiqish

for-har bir tsikldan foydalanish:
Keling, har bir tsikl uchun oldingi dasturni qanday bajarishni ko'rib chiqaylik.
using System;
namespace LogicalPrograms
{
public class Program
{
static void Main()
{
Console.Write("Enter a string to Check Palindrome : ");
string name = Console.ReadLine();
string reverse = string.Empty;
foreach (char c in name)
{
reverse = c + reverse;
}
if (name.Equals(reverse, StringComparison.OrdinalIgnoreCase))
{
Console.WriteLine($"{name} is Palindrome");
}
else
{
Console.WriteLine($"{name} is not Palindrome");
}
Console.ReadKey();
}
}
}
Chiqish

C# da Palindrome String dasturini amalga oshirishning yana bir yondashuvi:
Quyidagi misolda birinchi navbatda satrni belgilar massiviga aylantiramiz. Keyin Array sinfining Reverse usulidan foydalanib, biz belgilar massivining elementlarini teskari aylantiramiz. Belgilar massivining elementlarini teskari o'zgartirgandan so'ng, biz ushbu massivdan satr hosil qilamiz. Va nihoyat, biz ushbu yangi yaratilgan satrni asl satr bilan solishtiramiz va agar ikkala satr ham bir xil bo'lsa, uni Palindrom deb chop qilamiz, biz uni Palindrom emas deb chop qilamiz.
using System;
namespace LogicalPrograms
{
public class Program
{
static void Main()
{
Console.Write("Enter a string to Check Palindrome : ");
string name = Console.ReadLine();
char[] nameArray = name.ToCharArray();
Array.Reverse(nameArray);
string reverse = new string(nameArray);
if (name.Equals(reverse, StringComparison.OrdinalIgnoreCase))
{
Console.WriteLine($"{name} is Palindrome");
}
else
{
Console.WriteLine($"{name} is not Palindrome");
}
Console.ReadKey();
}
}
}
Chiqish

Xulosam.