DEV Community: Dilbar

CS50 - Week 6

Dilbar — Fri, 03 Jan 2025 12:12:47 +0000

Python

Python - foydalanish uchun qulay, ko'p qirrali dasturlash tili bo'lib, dasturlashga yangi kirganlar uchun ham, soha mutaxassislari uchun ham zo'r tanlov hisoblanadi.
C tilidan farqli o‘laroq, Python interpretatsiya qilinadigan til bo‘lib, unda dasturni alohida kompilyatsiya qilish shart emas. Buning o‘rniga dasturni Python interpretatorida ishga tushiriladi.

C tilida yozilgan "hello, world" xabarini ekranga chiqaruvchi kod Python tilida quyidagicha ifodalanadi:

print("hello, world")

E’tibor beradigan bo'lsak bunda hech qanday nuqtali vergul yo‘q va hech qanday kutubxona talab qilinmaydi. Pythonda C tilida ancha murakkab bo‘lgan kodlarni nisbatan oddiylik bilan amalga oshirishi mumkin.

O‘zgaruvchini e’lon qilish (Variable declaration) jarayoni Python tilida soddalashtirilgan. Masalan, C tilida o'zgaruvchini int counter = 0; kabi e'lon qilinadi. Python tilida esa o‘zgaruvchining turini e’lon qilish talab qilinmaydi: counter = 0.

Python’da ma’lumot turlarini aniq ko‘rsatish shart emas, uni interpretatorning o'zi o'zgaruvchining qiymatiga qarab aniqlashtirib oladi.
Python’da odatda quyidagi ma'lumot turlar qo‘llaniladi:

bool
float
int
str

C tilidagi kabi long va double turlari Python'da mavjud emas. Python katta va kichik sonlar uchun qaysi ma’lumot turini ishlatish kerakligini o‘zi hal qiladi.

Python’da qo'llaniladigan boshqa ma’lumot turlariga quyidagilar kiradi:

range
list
tuple
dict
set

Bu ma’lumot turlarining har birini C tilida ham amalga oshirish mumkin, biroq Python’da ularni yanada soddaroq tarzda qo‘llash imkoniyati mavjud.

Shart operatorlari

Python'da shart operatorlaridan foydalanganda qavslar - () majburiy emas.
Python'da {} o‘rniga indentatsiya ishlatiladi.
else if C'da ishlatilsa, Python'da buning o‘rniga elif qo‘llaniladi.
if, elif va else operatorlaridan keyin qo'sh nuqta : qo‘yiladi.

from cs50 import get_int

x = get_int("x ni kiriting: ")
y = get_int("y ni kiriting: ")

if x < y:
    print("x soni y sonidan kichik")
elif x > y:
    print("x soni y sonidan katta")
else:
    print("x soni y soniga teng")

C'da || bilan ifodalanadigan "yoki" mantiqiy operatori Python'da or bilan almashtiriladi.
Python'da char o‘rniga str ishlatiladi, bu esa bitta belgi yoki satr bilan ishlash imkonini beradi.

from cs50 import get_string
s = get_string("Ma'lumotlar o'zgartirilishiga rozimisiz? ")

if s == "Y" or s == "y":
    print("Ha.")
elif s == "N" or s == "n":
    print("Yo'q.")

Takrorlash operatorlari

Python’da takrorlanish operatorlari (loops) sintaksisi C ga juda o‘xshash, lekin sodda va tushunarliroq.
while sikli yordamida "meow" xabarini ekranga chiqaramiz:

i = 0
while i < 3:
    print("meow")
    i += 1

for sikli yordamida yuqoridagi kodni yana ham soddalashtirishimiz mumkin:

for i in range(3):
    print("meow")

Bu yerda ining qiymatini Python avtomatik ravishda oshirib boradi.
Shuningdek, yuqoridagi kodni quyidagicha yozishimiz mumkin:

def main():
    meow(3)


def meow(n):
    for i in range(n):
        print("meow")


main()

Bunday yondashuv kodni modullashtiradi.

List (Ro'yxat)

List yordamida bir o'zgaruvchida ko'p qiymatlar saqlashimiz mumkin. Listlarning elementlariga indexsi orqali murojaat qila olamiz.

scores = [72, 73, 33]

# O'rtacha qiymatni topamiz
average = sum(scores) / len(scores)
print(f"Average: {average}")

len() metodi yordamida listing uzunligini, ya'ni elementlar sonini aniqlaymiz.
sum() metodi yordamida sonlardan iborat bo’lgan listning elemtlari yig’indisini hisoblaymiz.

Foydalanuvchidan qiymatlarni olish uchun sikldan foydalanish mumkin:

from cs50 import get_int

# Foydalanuvchidan qiymatlarni kiritishni so'raymiz
scores = []
for i in range(3):
    score = get_int("Score: ")
    scores.append(score)

# O'rtacha qiymatni topamiz
average = sum(scores) / len(scores)
print(f"Average: {average}")

append metodi listga yangi qiymat qo‘shadi.

Python’da list ichida qiymatni qidirish uchun sikldan foydalanish yoki qisqaroq usuldan foydalanish mumkin:

# Ismlar ro'yxati
names = ["Carter", "David", "John"]

# Foydalanuvchidan ism kiritishni so'raymiz
name = input("Name: ")

# Ro'yxatdan qidiramiz
if name in names:
    print("Topildi")
else:
    print("Topilmadi"

in operatori list ichida qaralayotgan qiymat bor-yo‘qligini tekshiradi.

Dictionary (Lug'at)

Dictionary — bu kalit-qiymat juftliklari bo‘lib, qidiruv jarayonini tezlashtiradi.

from cs50 import get_string

people = {
    "Carter": "+1-617-495-1000",
    "David": "+1-617-495-1000",
    "John": "+1-949-468-2750",
}

# Kiritilgan ismni qo'yxatdan qidiramiz
name = get_string("Name: ")
if name in people:
    print(f"Telefon raqam: {people[name]}")
else:
    print("Topilmadi")

people[name] orqali lug‘at ichidan mos qiymat olinadi.
Lug‘atning qidirish tezligi odatda O(1).

Buyruq Qatori Argumentlari

Python’da sys kutubxonasi yordamida buyruq qatori argumentlarini ishlatish mumkin:

from sys import argv

if len(argv) == 2:
    print(f"salom, {argv[1]}")
else:
    print("salom, dunyo")

argv - argumentlar ro‘yxatini o‘z ichiga oladi, birinchi element esa fayl nomidir.
Barcha argumentlarni ekranga chiqaramiz:

from sys import argv

for arg in argv:
    print(arg)

Dastur qanday holatda yakunlagnanini bildirish uchun ma’lum chiqish kodlari (exit status) dan foydalanamiz:

import sys

if len(sys.argv) != 2:
    print("Buyruq qatori argumentini kiriting.")
    sys.exit(1)

print(f"salom, {sys.argv[1]}")
sys.exit(0)

sys.exit() yordamida chiqish kodi qaytariladi (masalan, 0 — dastur muvaffaqiyatli yakunlanganligini bildiradi).

Ushbu maqolada CS50x 2024 manbasidan foydalanilgan.

CS50 - Week 5

Dilbar — Fri, 27 Dec 2024 06:27:30 +0000

Ma'lumot tuzilmalari

Ma'lumot tuzilmalari - xotiradagi ma'lumotlarni tashkil qilish shakllaridir. Xotirada ma'lumotlarni tashkil qilishning ko‘plab usullari mavjud.

Abstrakt ma'lumot tuzilmalari – bu biz konseptual tarzda tasavvur qiladigan tuzilmalardir. Ushbu abstrakt tuzilmalar bilan tanishish kelgusida ma'lumot tuzilmalarini amaliyotda amalga oshirishni osonlashtiradi.

Stack va Queue

Queue – bu abstrakt ma'lumot tuzilmalarining bir shakli.
Queue ma'lumot tuzilmasi FIFO (First In First Out, "birinchi qo'shilgan element birinchi chiqadi") qoidasi bo‘yicha ishlaydi.
Buni attraksionda navbatda turgan odamlar misolida tasavvur qilish mumkin: navbatda birinchi bo‘lgan odam birinchi bo‘lib kiradi, oxirgi bo‘lgan esa oxirgi kiradi.

Queue'lar bilan quyidagi operatsiyalarni bajarish mumkin:

Enqueue: navbatning oxiriga yangi element qo‘shish.
Dequeue: navbatning boshidan elementni o'chirish.

Stack ma'lumot tuzilmasi esa LIFO (Last In First Out, "oxirgi qo'shilgan element birinchi chiqadi") qoidasi bo‘yicha ishlaydi.
Masalan, oshxonada laganlarni ustma-ust taxlash: eng oxirgi qo‘yilgan lagan birinchi olinadi.

Stack quyidagi operatsiyalarga ega:

Push: stack'ga yangi element qo‘yish.
Pop: stack'dan elementni o'chirish.

Massiv

Massiv – ma'lumotlarni xotirada ketma-ket saqlash usulidir. Massivni quyidagicha tasavvur qilish mumkin:

Xotirada boshqa dasturlar, funktsiyalar va o'zgaruvchilar tomonidan saqlanadigan boshqa qiymatlar, shuningdek, avval foydalanilib, hozir foydalanilmayotgan keraksiz qiymatlar ham mavjud bo'lishi mumkin:

Agar massivga yangi element – 4ni qo‘shmoqchi bo‘lsak, yangi xotira ajratib, eski massivni unga ko‘chirishimiz kerak bo‘ladi. Ushbu yangi xotira keraksiz qiymatlar (garbage values) bilan to'la bo'lishi mumkin:

Massivga elementlarni ko'chirib, yangi qiymatni qo'shsak, ajratilgan yangi xotiradagi eski kearksiz qiymatlar ustiga yangi qiymatlar yoziladi:

Bu yondashuvning kamchiligi – har bir yangi element qo‘shilganda massivni to‘liq nusxalash kerak bo‘ladi.
Agar biz 4 ni xotirada boshqa joyga joylashtirsakchi? U holda, ta'rifga ko'ra, bu endi massiv bo'lmaydi, chunki 4 xotirada massiv elementlari bilan ketma-ket joylashmaydi.

Ba’zida, dasturchilar kerak bo‘lganidan ko‘proq xotira ajratadilar (masalan, 30 ta element uchun 300 ta joy ajratilishi). Ammo bu yomon dizayn hisoblanadi, chunki tizim resurslari bekor sarflanadi va ko‘p hollarda ortiqcha xotira kerak bo‘lmaydi. Shuning uchun xotirani aniq ehtiyojga mos ravishda ajratish muhimdir.

Linked List

Linked List - C dasturlash tilidagi eng kuchli ma’lumot tuzilmalaridan biridir. Ular turli xotira hududlarida joylashgan qiymatlarni bir ro‘yxatda birlashtirish imkonini beradi. Shuningdek, ro‘yxatni xohlaganimizcha dinamik tarzda kengaytirish yoki qisqartirish imkonini ham beradi.

Har bir node o'zida ikki qiymatni saqlaydi:

qiymat;
keyingi node'ning xotiradagi manzilini o'zida saqlovchi ko'rsatkich. Oxirgi node esa undan keyin boshqa element yo'qligini ko'rsatish uchun o'zida NULLni saqlaydi.

Linked list birinchi elementinining manzilini bir ko'rsatkich (pointer) ga saqlab qo'yamiz.

C dasturlash tilida node'ni quyidagicha yozishimiz mumkin:

typedef struct node
{
    int number;
    struct node *next;
}
node;

Linked list yaratish jarayonini ko'rib chiqamiz:

node *listni e'lon qilamiz:

node uchun xotira ajratamiz:

nodening qiymatni kiritamiz: n->number = 1:

nodening next ko'rsatkichini NULLga tenglaymiz: n->next = NULL:

listni nga tenglaymiz:

Xuddi shunday tartibda, 2 qiymatiga ega yangi nodeni yaratamiz:

Ikkala nodelarni bir-biriga bog'lash uchun nning next ko'rsatkichini listga tenglaymiz:

Va nihoyat, listni nga tenglaymiz. Endi bizda ikkita elementlardan tashkil topgan linked list mavjud:

C dasturlash tilida ushbu jarayonning kodini quyidagicha yozishimiz mumkin:

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(int argc, char *argv[])
{
    // Linked list'ni e'lon qilamiz
    node *list = NULL;

    // Har bir buyruq qatori argumenti uchun
    for (int i = 1; i < argc; i++)
    {
        // Argumentni butun songa o‘tkazamiz
        int number = atoi(argv[i]);

        // Yangi element uchun xotira ajratamiz
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = number;
        n->next = NULL;

        // Linked list'ning boshiga node'ni qo‘shamiz
        n->next = list;
        list = n;
    }

    // Linked list elementlarini ekranga chiqaramiz
    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }

    // Xotirani bo‘shatamiz
    ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

Linked list bilan ishlashda bir qancha kamchiliklar mavjud:

Ko‘proq xotira: har bir element uchun nafaqat elementning o‘z qiymatini, balki keyingi elementga ko‘rsatkichni ham saqlash kerak.
Elementlarni indeks orqali chaqirish: massivlarda ma’lum bir elementni indeks orqali chaqirishimiz mumkin, lekin linked list'da bu imkonsiz. Ma’lum bir elementning joylashuvini topish uchun birinchi elementdan boshlab barcha elementlarni ketma-ket ko'rib chiqish kerak bo'ladi.

Tree

Binary Search Tree (BST) – bu ma’lumotlarni samarali saqlash, qidirish va olish imkonini beruvchi ma’lumot tuzilmasidir.
Bizga saralangan sonlar ketma-ketligi berilgan bo'lsin:

Markazdagi elementni eng yuqoriga, markazdagi elementdan kichik qiymatlarni chap tomonga, katta qiymatlarni esa o‘ng tomonga joylashtiramiz:

Ko‘rsatkichlardan foydalanib har bir elementni bir-biri bilan bog'laymiz:

Quyidagi kod BST ni qanday amalga oshirishni ko‘rsatadi:

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

void free_tree(node *root);
void print_tree(node *root);

int main(void)
{
    // Ma'lumot tuzilmasini e'lon qilamiz
    node *tree = NULL;

    // 2 qiymatini qo'shamiz
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 2;
    n->left = NULL;
    n->right = NULL;
    tree = n;

    // 1 qiymatini ma'lumot tuzilmasining chap tomoniga qo'shamiz
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 1;
    n->left = NULL;
    n->right = NULL;
    tree->left = n;

    // 3 qiymatini ma'lumot tuzilmasining o'ng tomoniga qo'shamiz
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 3;
    n->left = NULL;
    n->right = NULL;
    tree->right = n;

    // Elementlarni ekranga chiqaramiz
    print_tree(tree);

    // Xotirani bo‘shatamiz
    free_tree(tree);
    return 0;
}

// Xotirani bo‘shatish funksiyasi
void free_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

// Elementlarni ekranga chiqarish funksiyasi
void print_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    print_tree(root->left);
    printf("%i\n", root->number);
    print_tree(root->right);
}

Har bir node uchun xotira ajratamiz va uning qiymati numberga saqlanadi, shunindek har bir node - left, va right ko'rsatkichlariga ega. print_tree funksiyasi har bir nodeni chapdan o‘ngga ketma-ket rekursiya orqali chop etadi. free_tree funksiyasi ma'lumot tuzilmasining barcha nodelarini rekursiv ravishda xotiradan bo‘shatadi.

BST ning afzalliklari:

Dinamizm: elementlarni samarali qo'shishimiz yoki o'chirishimiz mumkin.
Qidiruv samaradorligi: BST da ma'lum bir elementni qidirishga ketadigan vaqt O(log n) bo‘ladi, chunki har bir qidiruvda daraxtning yarmi qidiruvdan chiqarib tashlanadi.

BST ning kamchiliklari:

Treening muvozanati buzilgan bo‘lsa (masalan, barcha elementlar ketma-ket joylashsa), qidiruv samaradorligi O(n)ga tushib ketadi.
Har bir node uchun left va right ko‘rsatkichlarini ham saqlashni talab qiladi, bu kompyuterda xotira iste’molini oshiradi.

Dictionary

Dictionary - bu xuddi lug‘at kitoblarlar kabi, unda so‘z va uning ta’rifi bo‘lganidek, uning elementlari kalit (key) va qiymat (value) ga ega.

Dictionary'dan biror bir elementni so'rasak, u elementni bizga O(1) vaqtda qaytaradi. Dictionary'lar xeshlash orqali aynan shu tezlikni ta’minlay oladi.

Xeshlash – kirish massividagi ma'lumotlarni maxsus algoritm yordamida bitlar ketma-ketligiga aylantirish jarayonidir.

Xesh funksiyasi – bu ixtiyoriy uzunlikdagi satrdan aniq uzunlikdagi bitlardan iborat satrni hosil qiladigan algoritmdir.

Hash table – bu massivlar va linked list'larning ajoyib kombinatsiyasidir. Uni quyidagicha tasavvur qilishimiz mumkin:

Kolliziya (Collisions) – bu ikkita har xil kirish ma'lumotidan bir xesh qiymat hosil bo'lib qolishidir. Yuqoridagi rasmda kolliziya bo'lgan elementlar linked list sifatida bog'langan. Xesh funksiyasini yaxshilash orqali kolliziya bo'lish ehtimolini kamashtirish mumkin.

Xesh funksiyasiga oddiy bir misol:

#include <ctype.h>

unsigned int hash(const char *word)
{
    return toupper(word[0]) - 'A';
}

Ushbu maqolada CS50x 2024 manbasidan foydalanilgan.

CS50 - Week 4

Dilbar — Wed, 25 Dec 2024 14:10:21 +0000

Piksellar

Piksellar – bu rasmni tashkil etuvchi eng kichik rangli nuqtalardir.
Rasmni nollardan va birlardan iborat deb tasavvur qilsak, bunda nollar qora rangni, birlar esa oq rangni ifodalaydi:

RGB (Red, Green, Blue) – bu har bir rangning miqdorini ifodalovchi sonlar. Adobe Photoshop dasturida ushbu sozlamalarni ko‘ramiz:

Qizil, yashil va ko‘k ranglarining tanglangan miqdori rangni qanday o‘zgartirishini yuqoridagi rasmda ko‘rishimiz mumkin. Shuningdek, ushbu rasmda rang faqat uchta qiymat orqali emas, balki maxsus raqam va belgilardan tashkil topgan qiymat bilan ifodalanishini ham ko‘rishimiz mumkin. Masalan, 255 qiymati FF sifatida ko‘rsatilgan.

O‘n oltilik sanoq sistemasi (Hexadecimal)

O‘n oltilik sanoq sistemasi - sonlarni faqat 16 belgidan foydalanib yozishga asoslangan sanoq sistemasi. Ular quyidagilar:

0 1 2 3 4 5 6 7 8 9 A B C D E F

O‘n oltilik sanoq sistemasida har bir ustun 16 darajasini ifodalaydi.
0 – 00 sifatida
1 – 01 sifatida
9 – 09 sifatida
10 – 0A sifatida
15 – 0F sifatida
16 – 10 sifatida
255 – FF sifatida ifodalanadi, chunki 16 x 15 (yoki F) 240 ga teng, unga yana 15 qo‘shilganda 255 bo‘ladi. Bu o‘n oltilik sanoq sistemasida ifodalash mumkin bo‘lgan ikki xonali eng katta son hisoblanadi.

O‘n oltilik sanoq sistemasi ma’lumotlarni qisqaroq ko‘rinishda ifodalash imkonini beradi. Shuning uchun u ma’lumotlarni ixchamroq ifodalash uchun qulay hisoblanadi.

Xotira (Memory)

Xotira bloklarini o‘n oltilik sanoq sistemasi orqali raqamlab chiqsak, ularni quyidagicha tasavvur qilishimiz mumkin:

Rasmdagi 10 bloki xotiradagi joylashuvni yoki 10 qiymatini ifodalayotganini aniqlash qiyin bo‘lishi mumkin. Shuning uchun, odatda, barcha o‘n oltilik sonlar 0x prefiksi bilan ifodalanadi:

Butun son n o'zgaruvchisiga 50 qiymatini beramiz:

#include <stdio.h>

int main(void)
{
    int n = 50;
    printf("%i\n", n);
}

Dasturning ushbu qiymatni xotirada qanday saqlayotganini quyidagicha tasavvur qilish mumkin:

C tilida xotira bilan ishlashga oid quyidagi operatorlar mavjud:

& – Xotiradagi biror qiymatning manzilini beradi.
* – Kompilyatorga xotiradagi joylashuvga borishni buyuradi.

Agar n o'rgaruvchimizning xotiradigi manzilini bilmoqchi bo'lsak, yuqoridagi kodimizni quyidagicha o'zgartirishimiz mumkin:

#include <stdio.h>

int main(void)
{
    int n = 50;
    printf("%p\n", &n);
}

%p – xotiradagi joylashuv manzilini ko‘rish imkonini beradi. &n esa kodni ishga tushirganimizda n o'zgaruvchisining xotiradagi 0x bilan boshlangan manzilini qaytaradi.

Ko'rsatkichlar (Pointers)

Ko‘rsatkich – bu qiymatning kompyuter xotirasidagi manzilini o‘zida saqlaydigan o‘zgaruvchi.

int n = 50;
int *p = &n;

Bunda p ko‘rsatkich bo‘lib, u butun son nning manzilini o‘z ichiga oladi.

Ko‘rsatkichlar odatda 8 baytli qiymat sifatida saqlanadi. p yuqoridagi rasmda 50 qiymatining manzilini saqlamoqda.
Ko‘rsatkichni xotiradagi bir manzildan boshqasiga ishora qiluvchi o‘q sifatida tasavvur qilishimiz mumkin:

String

String - bu oddiygina belgilar massividir. Masalan, string s = "HI!"ni kompyuter xotirasida quyidagicha tasvirlash mumkin:

s deb nomlangan ko‘rsatkich kompilyatorga berilgan qiymatning birinchi bayti qayerda joylashganini ko‘rsatadi:

string ma'lumot turidagi o'zgaruvchini quyidagicha yaratishimiz mumkin:

#include <stdio.h>

int main(void)
{
    char *s = "HI!";
    printf("%s\n", s);
}

Yuqoridagi kod s joylashuvdan boshlanadigan belgilar massivini ekranga chiqaradi.

String Comparison (Solishtirish)

string ma'lumot turidagi o'zgaruvchi qiymatlarni bir-biri bilan solishtiramiz:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Qiymatlarni olish
    char *s = get_string("s: ");
    char *t = get_string("t: ");

    // Solishtirish
    if (s == t)
    {
        printf("Bir xil\n");
    }
    else
    {
        printf("Turlicha\n");
    }
}

Yuqoridagi kodimizda s va t o'zgaruvchilarimizga bir xil "Hi!" qiymatini bersak ham natija sifatida "Turlicha" xabari ekranga chiqadi.
Nega bunday bo'layotganligini bilish uchun s va t o'zgaruvchilarimizga bir xil qiymat berib, ularni kompyuter xotirasida quyidagicha tasvirlashimiz mumkin:

Demak, yuqoridagi kod aslida, s va t o'zgaruvchilarining xotiradagi manzillarini solishtirishga urinayotgan ekan, ularning qiymatlarini emas.

Copying (Nusxalash)

Quyidagi kod berilgan bo'lsin:

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // Qiymat kiritamiz
    string s = get_string("s: ");

    // Manzilini nusxalaymiz
    string t = s;

    // Birinchi harfini kattalashtiramiz
    t[0] = toupper(t[0]);

    // Ekranga chop etamiz
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

string t = s kodida s manzili tga nusxalanadi. Bu biz xohlagan natijani bermaydi, chunki qiymat nusxalanmadi – faqat uning manzili nusxalandi.

s va t bir xil xotira bloklariga ishora qilmoqda. sdan tga uning qiymatini nusxalay olmadik, balki ular bitta qatorni ko‘rsatib turgan ikkita ko‘rsatkichga aylanishdi.

malloc – dasturchiga ma’lum o‘lchamdagi xotira blokini ajratish imkonini beradi.
free – oldin ajratilgan xotira blokini bo‘shatishni kompyuterdan so‘raydi.
Kodni haqiqiy nusxa yaratish uchun quyidagicha o‘zgartiramiz:

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    // Qiymat kiritamiz
    char *s = get_string("s: ");

    // Yangi o'zgaruvchi uchun xotira ajratamiz
    char *t = malloc(strlen(s) + 1);
    if (t == NULL)
    {
        return 1;
    }

    // Qiymatni yangi o'zaruvchi uchun ajratilgan xotiraga nusxalaymiz
    for (int i = 0, n = strlen(s); i <= n; i++)
    {
        t[i] = s[i];
    }

    // Birinchi harfini kattalashtiramiz
    t[0] = toupper(t[0]);

    // Ekranga chop etamiz
    printf("s: %s\n", s);
    printf("t: %s\n", t);

    // Xotirani bo‘shatish
    free(t);
    return 0;
}

malloc(strlen(s) + 1) - s o'zgaruvchi uzunligiga birni qo‘shib, \0 belgisi uchun joy ajratadi. Keyin for sikli orqali s qiymatlari tga nusxalanadi.

Garbage Values (Keraksiz qiymatlar)

Agar kompilyatordan xotira bloki so‘rasak, bu xotiraning bo‘sh bo‘lishiga kafolat yo‘q. Ajratilgan xotira ilgari kompyuter tomonidan ishlatilgan bo‘lishi mumkin, shuning uchun u yerda keraksiz qiymatlar bor bo‘lishi ehtimoli mavjud:

#include <stdio.h>

int main(void)
{
    int scores[1024];
    for (int i = 0; i < 1024; i++)
    {
        printf("%i\n", scores[i]);
    }
}

Ushbu kodni ishga tushirganimizda, massiv uchun 1024 ta xotira joyi ajratiladi, lekin for sikli yordamida massiv elementlarining qiymatlarini ekranga chiqarganimizda ularning hammasi ham 0 qiymatga ega bo'lmasligini ko'ramiz.

Kompyuterdan har doim biror-bir o'zgaruvchi uchun xotira ajratishni so'raganimizda, unga 0 yoki boshqa qiymat berib boshlang'ich holatga keltirish yaxshi amaliyot hisoblanadi.

Ushbu maqolada CS50x 2024 manbasidan foydalanilgan.

CS50 - Week 3

Dilbar — Tue, 24 Dec 2024 09:31:03 +0000

Algoritm - bu muammoni hal qilish uchun aniq ketma-ketlikda berilgan ko'rsatmalar to'plami. Algoritmlar bir-biridan tezligi va qancha xotira egallashi bilan farq qiladi. Dasturlash jarayonida aksar algoritmlar ma'lumotlarni qidirish (searching) va tartiblashga (sorting) borib taqaladi. Keling, ma'lumotlarni qidirish algoritmlari bilan tanishamiz:

Chiziqli qidiruv (Linear search)

Bizga quyidagi massiv berilgan bo'lsin:

[20, 500, 10, 5, 100, 1, 50]

Massivni tasavvur qilishda uni quyidagi kabi yonma-yon turgan yettita qizil shkaf sifatida ko‘rish mumkin:

Ushbu massivdan 50 sonini topishimiz kerak. Kompyuter 50 sonini topish uchun har bir shkafni tekshirishi kerak. Ushbu jarayonni, ya’ni massiv ichida ma’lum bir raqamni, belgini yoki boshqa elementni izlashni "qidiruv" deb ataymiz.
Biz massivimizni algoritmga topshirib, algoritm orqali shkaflarni ochib, 50 raqami bor-yo‘qligini aniqlashni so‘rashimiz mumkin. Natijada, algoritm bizga “ha” yoki “yo‘q” (true yoki false) deb javob beradi.

Quyidagi kabi ko‘rsatmalar yordamida algoritmni tuzishimiz mumkin:

Chapdan o‘ngga har bir eshikni tekshirish:
    Agar 50 soni bor bo‘lsa:
        Ha deb qaytaramiz (return true)
Yo‘q deb qaytaramiz (return false)

Yuqoridagi ko‘rsatmalar inson o‘qishi uchun mo‘ljallangan pseudokod bo‘lib, kompyuterga topshiriladigan buyruqlarning oddiyroq ko‘rinishidir.

Chiziqli qidiruv algoritmini quyidagi kod yordamida C tilida amalga oshirishimiz mumkin:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Butun sonlardan iborat massiv berilgan
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};

    // Kiritilgan sonni massivdan qidiramiz
    int n = get_int("Number: ");
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == n)
        {
            printf("Topildi\n");
            return 0;
        }
    }
    printf("Topilmadi\n");
    return 1;
}

Bu yerda for sikli yordamida chiziqli qidiruv amalga oshirilmoqda.
return 0 - dastur muvaffaqiyatli tugaganini bildiradi va dasturdan chiqiladi.
return 1 - dasturda xatolik yuz berganligini bildiradi.

Binar qidiruv (Binary search)

Binar qidiruv – bu 50 raqamini izlashda qo‘llaniladigan yana bir algoritm.
Agar massivdagi qiymatlar o'sish tartibida saralangan bo‘lsa, binar qidiruvning pseudokodini quyidagicha keltirishimiz mumkin:

Agar tekshiriladigan element qolmagan bo‘lsa:
    Yo‘q deb qaytaramiz (return false)
Agar massivning[o‘rta elementi] 50 soniga teng bo‘lsa:
    Ha deb qaytaramiz (return true)
Agar massivning[o‘rta elementi] > 50:
    Massivning chap yarmidan qidiramiz
Agar massivning[o‘rta elementi] < 50:
    Massivning o‘ng yarmidan qidiramiz

Big O notatsiyasi

Algoritmning ishlashiga ketadigan vaqtini tahlil qilish uchun Big O notatsiyasidan foydalaniladi. Quyidagi grafikni ko‘rib chiqamiz:

"Kiritiladigan ma'lumot hajmi" – x o‘qi; "Yechim uchun vaqt" – y o‘qi;
Algoritmning samaradorligi uning egri chizig‘ining shakliga qarab aniqlanadi:
O(n²) - eng yomon ishlash vaqti hisoblanadi.
O(log n) - eng tezkor ishlash vaqtidir.

Chiziqli qidiruv algoritmi ishlalishiga ketadigan vaqt - O(n), chunki eng yomon holatda n qadam talab qilinishi mumkin.
Binar qidiruv algoritmi ishlashiga ketadigan vaqt esa O(log n), chunki eng yomon holatda qadamlar soni tobora kamayib boradi.

Dasturchilarni qiziqtiradigan ikkita holat mavjud:

Eng yomon holat yoki yuqori chegarasi (upper bound).
Eng yaxshi holat yoki quyi chegarasi (lower bound).

Ω belgisi algoritmning eng yaxshi holatini (quyi chegarani) belgilash uchun ishlatiladi, masalan, Ω(n).

Θ belgisi esa yuqori va quyi chegaralar bir xil bo‘lgan holatni belgilaydi, ya’ni eng yaxshi va eng yomon ishlash vaqtining bir xil bo‘lishi.

Saralash algoritmlari (Sorting)

Saralash – bu tartiblanmagan qiymatlar ro‘yxatini tartiblangan holda o‘zgartirish jarayonidir.
Massiv tartiblangan holatda bo‘lsa, undan ma'lum bir elementni qidirish kompyuter uchun ancha yengil bo‘ladi. Masalan, binar qidiruv (binary search) tartiblangan massivda ishlaydi, ammo tartiblanmagan massivda ishlamaydi.

Saralash algoritmlarining ko‘plab turlari mavjud. Ulardan biri tanlash usuli (selection sort) ni ko'rib chiqamiz. Bizga quyidagicha massiv berilgan bo'lsin:

Tanlash usuli algoritmining pseudokodi quyidagicha bo'ladi:

i = 0 dan n-1 gacha:
    numbers[i] va numbers[n-1] orasidagi eng kichik sonni topamiz
    Eng kichik sonni numbers[i] bilan almashtiramiz

Bosqichlar tahlili:

Birinchi marta massiv elementlari bo‘ylab yurish n - 1 qadam talab qiladi.
Ikkinchi marta esa n - 2 qadam talab qilinadi.
Ushbu mantiq davom ettirilsa, kerakli qadamlar quyidagicha ifodalanishi mumkin:

(n - 1) + (n - 2) + (n - 3) + ... + 1

Bu formulani soddalashtirish orqali quyidagini olamiz: n(n-1)/2 yoki O(n²).
Demak, tanlash usuli algoritmi eng yomon holatda O(n²) tartibida saralar ekan. Hatto barcha qiymatlar tartiblangan bo‘lsa ham, qadamlar soni o‘zgarmaydi, ya’ni eng yaxshi holat ham O(n²) tartibida ishlaydi.

Pufakchali saralash algoritmi (Bubble sort)

Pufakchali saralash — yana bir saralash algoritmi bo'lib, bunda elementlarni qayta-qayta joylarini almashtirib, kattaroq qiymatlarni oxiriga “ko‘taramiz”.

Pufakchali saralash algoritmining pseudokodi quyidagicha bo'ladi:

n–1 marta takrorlaymiz:
    0 dan n–2 gacha har bir i uchun:
        Agar numbers[i] va numbers[i+1] noto‘g‘ri tartibda bo‘lsa:
            Ularni joyini almashtiramiz
    Agar almashtirishlar qolmagan bo‘lsa:
        Dasturdan chiqamiz

Massivni tartiblash davomida shuni bilamizki, uning ko‘proq qismi tartiblanib boradi, shuning uchun faqat hali tartiblanmagan juftliklarni tekshirishning o'zi kifoya qiladi.
Shuning uchun pufakchali saralash algoritmi eng yomon holatda massiv tartiblanmagan bo'lsa O(n²), eng yaxshi holatda massiv allaqachon tartiblangan bo‘lsa O(n) tartibida ishlaydi.

Saralash algoritmlari qanday holatda qanday ishlashini ushbu sahifada vizual ko'rishimiz mumkin.

Ushbu maqolada CS50x 2024 manbasidan foydalanilgan.

CS50 - Week 2

Dilbar — Fri, 14 Jun 2024 10:19:09 +0000

Kompilyatsiya qilish

Shifrlash - bu oddiy matnni begona ko'zlardan yashirish jarayoni. Deshifrlash esa, shifrlangan matnni inson o'qiy oladigan shaklga qaytarishdir.
Shifrlangan matn quyidagicha ko'rinishi mumkin:

Kompilyator - dastlabki kodni kompyuter tushunadigan mashina kodiga aylantiradigan maxsus kompyuter dasturi.
Bizga hello.c faylida quyidagi berilgan bo'lsin:

#include <stdio.h>

int main(void)
{
    printf("hello, world\n");
}

Kompilyator yuqoridagi kodni olib, quyidagi mashina kodiga aylantiradi:

VS Code - to'liq nomi Visual Studio Code, bu Microsoft tomonidan ishlab chiqilgan bepul va ochiq manbali kod muharriri hisoblanadi. CS50 kursi talabalari uchun cs50.dev saytida VS Code kod muharriri sozlangan bo'lib, unda kompilyator sifatida clang ni ishlatadi.
clang – bu C, C++, va boshqa dasturlash tillari uchun mo‘ljallangan yuqori samarali va tezkor kompilyator hisoblanadi.

Rasmda chap tomonda fayllarimizni topishimiz mumkin. Shuningdek, o'rtada matn muharriri joylashgan. O'ng tomon pastda buyruqlar qatori interfeysi (CLI) yoki terminal oynasi deb ataladigan soha mavjud bo'lib, bu yerdan kompyuterga buyruqlarni yuborishimiz mumkin.

make hello buyrug'ini VS Code kod muharrining terminal oynasida kiritadigan bo'lsak, u clang ni chaqiradi va hello.c faylimizni kompilyatsiya qiladi. Dasturimizni ./hello buyrug'i orqali ishga tushura olamiz.

Kompilyatsiya qilish bir nechta qadamlarni o'z ichiga oladi:

oldindan qayta ishlash (preprocessing) - bu koddagi sarlavha fayllari (masalan, #include <stdio.h>) faylimizga nusxalanib, joylashtiriladigan bosqichdir:

int printf(string format, ...);

int main(void)
{
    printf("hello, world\n");
}

kompilyatsiya qilish (compiling) - bu dasturni assembler kodiga aylantirishdir:

yig'ish (assembling) - kompilyatorning assembler kodini mashina kodiga aylantirish:

bog'lash (linking) - bu bosqichda kodimizga kiritilgan kutubxonalar kodlari ham mashina kodiga aylantiriladi va birlashtiriladi:

"Debug" qilish

Har kim ham dasturlash jarayonida xatolar qiladi. Quyidagi ataylab xato bilan yozilgan buggy.c faylini ko'rib chiqsak:

#include <stdio.h>

int main(void)
{
    for (int i = 0; i <= 3; i++)
    {
        printf("#\n");
    }
}

Ushbu kodni ishga tushirganimizda, ekranga uchta belgi o'rniga to'rtta belgi ekranga chiqadi. printf funksiyasi yordamida dasturimizning qayerida xato qilganimizni qanday topishni ko'rib chiqamiz:

#include <stdio.h>

int main(void)
{
    for (int i = 0; i <= 3; i++)
    {
        printf("i - bu %i\n", i);
    }
}

Yuqoridagi kodimizni ishga tushirsak, terminalda quyidagi matnlar paydo bo'ladi:

Buni ko'rib, kodni quyidagicha to'g'rilash kerakligini tushunamiz:

#include <stdio.h>

int main(void)
{
    for (int i = 0; i < 3; i++)
    {
        printf("#\n");
    }
}

Ya'ni, <= (kichik yoki teng) belgisini < (kichik) belgisiga o'zgartirdik.
Dasturdagi xatolarni to'g'rilashning ikkinchi vositasi "debugger" deb atalib, u dasturchilar tomonidan koddagi xatolarni kuzatishda yordam berish uchun yaratilgan dasturiy vositadir.
VS Code da oldindan sozlangan debugger mavjud. Ushbu debuggerdan foydalanish uchun quyidagi bosqichlarni bajaramiz:

"Breakpoint" qo'yish - kod satrining chap tomoniga bosganimizda qizil nuqta (to'xtash belgisi) paydo bo'ladi va u kompilyatorga ushbu kod qismida to'xtab, nima sodir bo'layotganini ko'rib chiqishimiz mumkinligini bildiradi.

Debuggerni ishga tushirish - terminalda debug50 ./buggy buyrug'ini bersak debugger ishga tushadi va breakpoint qo'yilgan satrda kod bajarilishi to'xtaydi.
Kodni tahlil qilish - barcha mahalliy o'zgaruvchilar chap yuqori burchakda ko'rsatiladi. Ekranning yuqorisida joylashgan "step over" tugmasini bosib, kodimizni birma-bir tekshirib chiqamiz. Bunda i o'zgaruvchisining qiymati qanday oshayotganini ko'rishimiz mumkin bo'ladi.

Debugger bizga qayerda xato borligini ko'rsatmasa ham, kodning qanday ishlashini asta-sekin ko'rib chiqishimizga yordam beradi.

Massivlar

Kompyuterimiz ichida mavjud bo'lgan xotira miqdori cheklangan.

Kompyuter xotirasida ma'lum turdagi ma'lumotlar qanday saqlanishini tasavvur qilaylik. Masalan, char turi faqat 1 bayt xotira talab qiladi va u quyidagicha ko'rinishi mumkin:

Shuningdek, 4 bayt xotira talab qiladigan int turi esa quyidagicha ko'rinishi mumkin:

Massivlar - ma'lumotlarni xotirada ketma-ket saqlash usulidir. Shuning uchun bu ma'lumotlarni osonlik bilan olish mumkin.
int scores[3] - bu kompilyatorga int turidagi uchta butun sonlarni saqlash uchun ketma-ket uchta joy ajratish buyrug'idir. Keling, ushbu ballarning o'rta arifmetigini topuvchi dastur yaratamiz:

#include <stdio.h>

int main(void)
{
    // Ballar qiymatini kiritish
    int scores[3];
    scores[0] = 72;
    scores[1] = 73;
    scores[2] = 33;

    // O'rta arifmetigini hisoblash va ekranga chiqarish
    printf("Average: %f\n", (scores[0] + scores[1] + scores[2]) / 3.0);
}

scores[0] - massivning 0-indexsida turgan qiymatini kompyuter xotirasidan ko'rib chiqadi. Keling, scores massivi xotirada qanday joylashganini ko'ramiz:

Keling, yuqoridagi kodimizni abstraktlaymiz:

#include <cs50.h>
#include <stdio.h>

// O'zgarmas butun son
const int N = 3;

// Funksiya prototipi
float average(int length, int array[]);

int main(void)
{
    // Ballar qiymatini kiritish
    int scores[N];
    for (int i = 0; i < N; i++)
    {
        scores[i] = get_int("Score: ");
    }

    // O'rta arifmetikni ekranga chiqarish
    printf("Average: %f\n", average(N, scores));
}

float average(int length, int array[])
{
    // O'rta arifmetikni hisoblash
    int sum = 0;
    for (int i = 0; i < length; i++)
    {
        sum += array[i];
    }
    return sum / (float) length;
}

for sikli orqali scores[i] yordamida massiv elementlariga qiymat kiritamiz. O'zgarmas butun son N e'lon qilingan. Shuningdek, average funksiyasi e'lon qilingan va u int array[] qabul qiladi, ya'ni kompilyator massivni ushbu funksiyaga o'tkazadi.
Demak, massivlar nafaqat konteyner bo'lishi, shu bilan birga ular funksiyalar orasida o'tkazilishi mumkin ekan.

String

String - bu char turidagi o'zgaruvchilar massividir, ya'ni belgilar massivi. Bunda u ma'lum belgi bilan boshlanib, satr tugaganini bildirish uchun maxsus NUL belgisi bilan tugaydi:

Keling, char turidagi o'zgaruvchilarni ekranga chiqaruvchi dastur yozamiz:

#include <stdio.h>

int main(void)
{
    char c1 = 'H';
    char c2 = 'I';
    char c3 = '!';

    printf("%c%c%c\n", c1, c2, c3);
}

Agar %c format kodini %i bilan almashtirsak, berilgan char turidagi o'zgaruvchilarning ASCII kodlari chop etiladi:

#include <stdio.h>

int main(void)
{
    char c1 = 'H';
    char c2 = 'I';
    char c3 = '!';

    printf("%i %i %i\n", c1, c2, c3);
}

string qanday ishlashini yaxshiroq tushunish uchun kodimizni quyidagicha o'zgartiramiz:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string s = "HI!";
    printf("%c%c%c\n", s[0], s[1], s[2]);
}

Bunda string turidagi s o'zgaruvchimiz aslida massiv bo'lganligi sababli, 0-, 1- va 2-indeksdagi qiymatlarni chaqirishimiz mumkin.
Oldingidek, %c format kodini %i bilan almashtirishimiz mumkin:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string s = "HI!";
    printf("%i %i %i %i\n", s[0], s[1], s[2], s[3]);
}

Bunda string turidagi s o'zgaruvchisi belgilarining ASCII kodlari hamda NUL belgisi ekranga chiqadi.

String uzunligi

C tilida massivning uzunligini aniqlash muammosi mavjud. string ham aslida belgilar massividir. Keling string turidagi o'zgaruvchi uzunligini aniqlaymiz:

#include <cs50.h>
#include <stdio.h>

int string_length(string s);

int main(void)
{
    // Foydalanuvchining ismini so'rash
    string name = get_string("Name: ");
    int length = string_length(name);
    printf("%i\n", length);
}

int string_length(string s)
{
    // Belgilar sonini NUL belgisigacha hisoblash
    int n = 0;
    while (s[n] != '\0')
    {
        n++;
    }
    return n;
}

Bunda string turidagi name o'zgaruvchisining uzunligi NUL belgisi topilgunga qadar hisoblanyabdi.
Bu dasturlashda juda keng tarqalgan muammo bo'lganligi sababli, boshqa dasturchilar string uzunligini hisoblashni osonlashtirish uchun string.h kutubxonasida tayyor strlen funksiyasini yaratganlar va biz uni shunchaki chaqirib ishlatishimiz mumkin:

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // Foydalanuvchining ismini so'rash
    string name = get_string("Name: ");
    int length = strlen(name);
    printf("%i\n", length);
}

string.h kutubxonasi kodning yuqori qismida e'lon qilingan va foydalanuvchi kiritgan name o'zgaruvchisining uzunligini hisoblash uchun tayyor strlen funksiyasidan foydalanilyabdi.

Ushbu maqolada CS50x 2024 manbasidan foydalanilgan.

CS50 - Week 1

Dilbar — Fri, 07 Jun 2024 11:20:11 +0000

بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم
Mashinalar faqat binarni tushunadi. Biz kompyuter uchun biror-bir inson o'qiy oladigan ko'rsatmalar ro'yxatini yozganimizda, mashinalar faqat biz hozir mashina kodi deb ataydigan narsani tushunadilar. Bu mashina kodi faqat 1 va 0 lardan iboratdir.
Kompilyator deb ataladigan maxsus dastur yordamida dastlabki kodni mashina kodiga aylantira olamiz.

Yaxshi kodni 3 asosga ko'ra baholashimiz mumkin:

to'g'rilik (kod istalgan natijani beryabdimi?),
dizayni (kod dizayni yoki strukturasi yaxshi tuzilganmi?),
stil (kod qanchalik chiroyli ko'rinishda yozilgan?).

Salom, dunyo!

C dasturlash tilida ekranga biror-bir matnni chiqarmoqchi bo'lsak, printf funksiyasidan foydalanamiz:

#include <stdio.h>

int main(void)
{
    printf("salom, dunyo\n")
}

printf funksiyasi salom, dunyo matnini ekranga chiqaradi. Undagi maxsus \ belgisi kompilyatorga keyingi keladigan belgi maxsus ko'rsatma ekanligini anglatadi. Undan keyin kelayotgan n belgisi esa "new line" (yangi qator) belgisini bildiradi.
Kodning birinchi qatoridagi ifoda stdio.h nomli kutubxona imkoniyatlaridan foydalanmoqchi ekanligimizni bildiruvchi juda maxsus buyruqdir. Bu kutubxona bizga printf funksiyasidan foydalanish imkonini beradi.
Kutubxonalar - bu bizning kodimizda foydalanishimiz mumkin bo'lgan tayyor funktsiyalar to'plamidir.

O'zgaruvchilar

Keling, foydalanuvchidan uning ismi nima ekanligini so'rab, unga salom beruvchi kodni C tilida yozamiz:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string answer = get_string("Ismingiz nima? ");
    printf("Assalomu alaykum, %s\n", answer);
}

CS50 kursi uchun maxsus ishlab chiqilgan cs50.h kutubxonasi imkoniyatlaridan ushbu kurs davomida foydalaniladi. Ulardan biri get_string funksiyasidir. get_string funksiyasi foydalanuvchi kiritgan matnni olish uchun ishlatiladi.
answer - bu biz o'zgaruvchi deb ataydigan maxsus foydalanuvchi kiritadigan matnni eslab qolish uchun ajratilgan joy. answer string turiga kiradi. Shuningdek, undan tashqari int, bool, char va boshqalar kabi ko'plab ma'lumotlar turlari mavjud.
%s - bu printf funksiyasiga qandaydir string turidagi o'zgaruvchini qabul qilib olishga tayyorgarlik ko'rishini bildiruvchi format kodi deb ataladigan to'ldiruvchidir.
Shuningdek, boshqa ma'lumot turlari uchun ham format kodlari mavjud, masalan:
%i - int (butun sonlar) uchun.

Shart operatorlari

Keling, foydalanuvchidan int turidagi x va y o'zgaruvchilarini kiritishini so'rab, kiritilgan sonlarni bir-biri bilan solishtiramiz:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    int x = get_int("x ni kiriting: ");
    int y = get_int("y ni kiriting: ");

    if (x < y)
    {
        printf("x soni y sonidan kichik\n");
    }
}

Bu yerda biz int (butun son) turidagi ikkita o'zgaruvchini, x va y o'zgaruvchilarini yaratyabmiz. Ularning qiymatlari cs50.h kutubxonasining get_int funksiyasi yordamida to'ldiriladi. Shart operatori yordamida x va y qiymatlarini bir-biriga solishtirib, natijaga qarab ekranga xabar chiqaryabmiz.

Blok-sxema - kompyuter dasturi qanday ishlashini tekshirishimiz mumkin bo'lgan usuldir. Bu usul yordamida biz kodimizning samaradorligini tekshirishimiz mumkin.
Yuqoridagi kodimizning blok-sxemasini ko'ramiz:

Dasturni quyidagi tarzda kodlash orqali yaxshilashimiz mumkin:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    int x = get_int("x ni kiriting: ");
    int y = get_int("y ni kiriting: ");

    if (x < y)
    {
        printf("x soni y sonidan kichik\n");
    }
    else if (x > y)
    {
        printf("x soni y sonidan katta\n");
    }
    else
    {
        printf("x soni y soniga teng\n");
    }
}

Endi barcha mumkin bo'lgan holatlar hisobga olinadi. Uning blok-sxemasini ko'ramiz:

Takrorlash operatorlari

Keling, 3 marta ekranga "meow" xabarini chiqaramiz:

#include <stdio.h>

int main(void)
{
    printf("meow\n");
    printf("meow\n");
    printf("meow\n");
}

Yozgan kodimiz to'g'ri ishlaydi, lekin undagi takrorlanishlarni oldini olib, dasturimizni quyidagicha yaxshilashimiz mumkin:

#include <stdio.h>

int main(void)
{
    int i = 0;
    while (i < 3)
    {
        printf("meow\n");
        i++;
    }
}

Bunda int turidagi i o'zgaruvchisi yaratilib, unga 3 qiymati berilgan. Keyin i < 3 bo'lgan vaqt davom etadigan while sikli yaratilgan. Har safar i++ ifodasi yordamida i sonimiz bittaga oshib boradi va qachonki i = 3 bo'lganida sikl to'xtaydi.
for sikli yordamida dasturimiz dizaynini yanada yaxshilashimiz mumkin:

#include <stdio.h>

int main(void)
{
    for (int i = 0; i < 3; i++)
    {
        printf("meow\n");
    }
}

for sikli uchta argumentni o'z ichiga oladi.
Birinchi argument: int i = 0 hisoblagichimizni noldan boshlaydi.
Ikkinchi argument: i < 3 - tekshirilayotgan shart.
Nihoyat, i++ argumenti har safar i sonimiz bittaga oshishini bildiradi.
Biz o'zimizning funksiyamizni yaratishimiz ham mumkin:

void meow(void)
{
    printf("meow\n");
}

void - funktsiya hech qanday qiymat qaytarmasligini bildiradi. Qavslar ichidagi (void) - funktsiya hech qanday parametr qabul qilmasligini bildiradi.
Ushbu yaratgan meow funksiyamizni asosiy funksiya ichida ishlatamiz:

#include <stdio.h>

void meow(void);

int main(void)
{
    for (int i = 0; i < 3; i++)
    {
        meow();
    }
}

void meow(void)
{
    printf("meow\n");
}

meow funksiyasini asosiy funksiya ichida chaqira olishimiz uchun funksiya prototipi kodning yuqori qismida void meow(void) sifatida berilgan.

Arifmetik operatorlar va akstraksiya

Keling, C tilida kalkulyator yasaymiz:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // x qiymati kiritilsin
    int x = get_int("x: ");

    // y qiymati kiritilsin
    int y = get_int("y: ");

    // Qo'shish amalini bajarish
    printf("%i\n", x + y);
}

get_int funktsiyasi yordamida foydalanuvchidan butun son bo'lgan x va y o'zgaruvchilariga qiymat berishi so'ralyabdi. Keyin printf funksiyasi butun son uchun format kodi - %i belgisi yordamida x + y qiymatini chop etadi.

Arifmetik operatorlar kompilyator tomonidan qo'llab-quvvatlanadigan matematik operatsiyalardir. C tilida arifmetik operatorlarga quyidagilar kiradi:

+ - qo'shish uchun;
- - ayirish uchun;
* - ko'paytirish uchun;
/ - bo'linish uchun;
% - bir sonni ikkinchi songa bo'lgandagi qoldiqni hisoblash uchun.

Abstraksiya - bu muammoni kichik-kichik bo'laklarga bo'lib hal qilish orqali kodimizni soddalashtirish san'ati.
Biz yuqoridagi kodimizni quyidagicha abstraktlashimiz mumkin:

#include <cs50.h>
#include <stdio.h>

int add(int a, int b);

int main(void)
{
    // x qiymati kiritilsin
    int x = get_int("x: ");

    // y qiymati kiritilsin
    int y = get_int("y: ");

    // Qo'shish amalini bajarish
    printf("%i\n", add(x, y));
}

int add(int a, int b)
{
    return a + b;
}

Bunda parametr sifatida a va b butun sonlarini qabul qilib oladigan va ularning yig'indisini qaytaradigan alohida add funksiyasi e'lon qilingan va asosiy funksiya ichida argument sifatida x va y butun sonlarini olib add(x, y) funksiyamiz chaqirilyabdi.

Kommentlar (izohlar)

Kommentlar - kompyuter dasturining asosiy qismlari bo'lib, yozgan kodimiz nima vazifa bajarayotganini ifodalovchi, boshqa dasturchilarga, shuningdek o'zimizga tushunarli hamda qisqa qilib qoldirgan izohlarimizdir. Kommentni yozish uchun shunchaki ikkita // beligisidan foydalanamiz:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Musbat butun son kiritilsin
    int n;
    do
    {
        n = get_int("Musbat butun son kiriting: ");
    }
    while (n < 1);
}

Ma'lumot turlari

Ma'lumotlar turlari o'zgaruvchida saqlanishi mumkin bo'lgan ma'lumotlar turini belgilaydi. Misol uchun, o'zgaruvchilar raqamlar, belgilar yoki mantiqiy qiymatlarni saqlashi mumkin. O'zgaruvchining turi kompyuterga ushbu ma'lumotlarni qanday boshqarishni aytadi.
C tilidagi umumiy maʼlumotlar turlari:

bool: rost (true) yoki yolg'on (false) kabi mantiqiy qiymatlarni saqlashi mumkin.
char: faqat bitta belgini saqlashi mumkin.
float: o'nlik qiymatlari bo'lgan haqiqiy son.
int: kasrsiz butun son.
long: int dan kattaroq butun sonni saqlashi mumkin, chunki u ko'proq bit ishlatadi.
string: belgilar ketma-ketligini saqlashi mumkin (masalan, so'z).

Har bir turning o'ziga xos chegaralari bor. Misol uchun, xotiradagi cheklovlar tufayli int ning eng yuqori qiymati 4294967295 bo'lishi mumkin. Agar biz int ni uning eng yuqori qiymatidan o'tkazib sanashga harakat qilsak, bu o'zgaruvchida noto'g'ri qiymat saqlanishiga (integer overflow) olib keladi.
Xotirani noto'g'ri ishlatish kodimizdagi xatolar yoki muammolarga olib kelishi mumkin. Muammolarni oldini olish uchun biz to'g'ri ma'lumot turidan foydalanayotganimizga ishonch hosil qilishimiz kerak.

Ushbu maqolada CS50x 2024 manbasidan foydalanilgan.

CS50 - Week 0

Dilbar — Tue, 02 Apr 2024 18:10:59 +0000

بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم

Garvard universiteti tomonidan taqdim etilgan o'sha mashhur kurs - CS50 kursini o'rganishni boshladim. O'rganish davomida o'rganganlarim, kerakli deb hisoblagan ma'lumotlarni sizlar bilan bo'lishib bormoqchiman. Ushbu kursda amerikalik professor David J.Malan tomonidan dasturlash tushunchalari, algoritmlar, ma'lumot tuzilmalari va umuman, kompyuterlar qanday paydo bo'lib, hozirgi holatga qanday kelib qolgan, barchasi aniq misollar bilan juda qiziqarli usulda tushuntirilgan.

Demak, boshladik!

Dasturlash

Dasturlash - bu kirish (input) ma'lumotini olib unga mos natija (output) yaratish, umuman olganda qandaydir mavjud muammoni yechish hisoblanadi.

Ikkilik sanoq sistemasi

Bugungi kunda kompyuterlar ikkilik (binary) deb ataladigan sanoq sistemasidan foydalanadi. Bit - ikkilik sanoq sistemasidagi raqamdir. Bir bit - o'chiq yoki yoniqlikni beradi.
Kompyuterlar faqat nol va birlar shaklida gaplashadi. Nol - o'chiqni, birlar esa yoniqlikni ifodalaydi. Kompyuterlarda millionlab, milliardlab shunday o'chiq yoki yoniq bo'lgan tranzistorlar ishlatilinadi.

Kompyuterlar raqamni ifodalash uchun sakkiz bit (bayt) dan foydalanadi. Masalan, 00000111 ikkilik sanoq sistemada 7 raqamini beradi. 11111111 esa 255 raqamini bildiradi.

ASCII (American Standard Code for Information Interchange)

Raqamlar birlar va nollar yordamida ikkilik sanoq sistemasida ifodalangani kabi, harflar ham bir va nol yordamida ifodalanadi! Raqamlar va harflarni ifodalovchi birlar va nollar o'rtasida o'xshashlik mavjudligi sababli, ASCII standarti yaratilingan.

Misol uchun, ushbu standartga ko'ra A harfi 65 raqami bilan belgilashga kelishilingan. Bu ikkilik sanoq sistemasida 01000001 ni ifodalaydi. Ikkilik sanoq tizimi bilan faqat 255 gacha hisoblash mumkinligi sababli ASCII bilan ifodalash mumkin bo'lgan belgilar soni cheklangan.

Unicode

Ikkilik sanoq tizimida 8 bitlikda odamlar tomonidan ifodalanishi mumkin bo'lgan barcha turli belgilarni ifodalash uchun raqamlar yetarli emasligi sababli, Unicode standarti kompyuterlar tomonidan uzatilishi va tushunilishi mumkin bo'lgan bitlar sonini kengaytirdi. Unicode nafaqat maxsus belgilarni, balki emojilarni ham o'z ichiga oladi.

Rangni ifodalash uchun ham nol va birlardan foydalanish mumkin.
RGB - qizil (red), yashil (green) va ko'k (blue) uchta raqamning kombinatsiyasidir.

Shuningdek, rasmlar oddiygina RGB qiymatlari to'plamidir.
Videolar esa ko'plab tasvirlar ketma-ketligidir.

Ushbu maqolada CS50x 2024 manbasidan foydalanilgan.

Algoritmni optimallashritish usullari

Dilbar — Sun, 09 Jul 2023 10:00:19 +0000

Intervyuda beriladigan masalalarni yechishda avvalambor, "Brute Force", ya'ni unchalik optimal bo'lmagan, lekin ishlaydigan yechim berish kerak. Keyinchalik shu "Brute Force" yechimni qanday qilib optimallashtirish mumkin? Aslida sizni intervyu qiladigan odam ham shuni kutib turadi va ko'p hollarda optimal yechimga olib boradigan ishoralar berishga harakat qiladi.
Buning birinchi usullaridan biri: "BUD".

BUD usuli

BUD - quyidagi so'zlarning bosh harflaridan tuzilgan:

Bottlenecks
Unnecessary work
Duplicated work

"Bottlenecks" - to'siqlar. Bu algoritm hisoblanishiga ketadigan vaqtni sekinlashtirayotgan qismidir.
Masalan: bizda mavjud ko'p qismli algoritmning 1-qismi berilgan massivni saralasin, 2-qismi esa saralangan massivdan ma'lum bir elementni topsin. Algoritm hisoblanishiga ketadigan vaqt 1-qismda O(n*log(n)), 2-qismda O(n) bo'lsin. Ko'rinib turibdiki, algorimning 1-qismi algoritm hisoblanish vaqtini sekinlashtiryapti. Agar biz uni optimallashtiradigan bo'lsak, algoritmni optimallashtirgan bo'lamiz.

Masala:
Butun sonlardan tashkil topgan va bo'sh bo'lmagan massiv berilgan bo'lsin. Massivda bir elementdan tashqari har bir element ikki martadan qatnashadi. Takrorlanmagan elementni topish va uni qaytarish kerak.

Yechish:
Birinchi bo'lib hayolga keladigan yechim quyidagicha bo'lishi mumkin:

function singleNumber (nums) {
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== nums[i - 1] && nums[i] !== nums[i + 1]) {
            return nums[i];
        }
    }
};

Demak, biz avvalambor berilgan massivimizni o'sish tartibida saralab oldik. JavaScriptning sort() metodi O(n*log(n)) o'rtacha hisoblash vaqtiga ega, bu yerda n massiv uzunligidir. Keyingi sikl esa har bir elementni tekshiradi va agar massiv elementi undan oldingi va keyingi elementlarga teng bo'lmasa, shu elementni qaytaradi. Bu sikl O(n) chiziqli hisoblash vaqtiga ega.
Funksiyaning umumiy hisoblash vaqti O(n*log(n)) + O(n) bo'lib, O(n*log(n))ga soddalashadi. Bu funksiyamizdagi hisoblash vaqtini sekinlashtirayotgan qismi - massivni saralagan qismimizdir. Umuman olganda, bizga massivni saralashimiz kerakmi? Masalani massivni saralamasdan ham yecha olamizmi?

Endi "Brute Force" yechimimizni optimallashtirishga o'tamiz.

function singleNumber(nums) {
  let singleNum = 0;

  for (let num of nums) {
    singleNum ^= num;
  }

  return singleNum;
}

Ushbu optimallashtirilgan algoritmimizda biz massivning har bir elementini ko'rib chiqyapmiz va bitli XOR operatoridan ^ foydalangan holda singleNum o'zgaruvchimizga qo'shib bormoqdamiz. Raqamni o'zi bilan XOR lash 0 qiymatini beradi, shuning uchun takroriy raqamlar mavjud bo'lganda, ular 0 bo'lib ketadi va faqatgina takrorlanmagan raqam qoladi. Bu esa umumiy O(n) hisoblash vaqtini oladi.

Unnecessary work - keraksiz ish. Biz algoritmimizda biror-bir keraksiz ishni amalga oshiryapmizmi?

Masala:
Quyidagi ikki xususiyatga ega (m x n) butun sonlar matritsasi berilgan:

Har bir qator kamaymaydigan tartibda tartiblangan.
Har bir satrning birinchi butun soni oldingi qatorning oxirgi butun sonidan kattaroqdir.

Masalan:

Butun son target berilgan bo'lsa, agar target matritsada bo'lsa, true, aks holda false qaytarish kerak.

Yechish:
"Brute Force" yechim quyidagicha bo'lishi mumkin:

function searchMatrix(matrix, target) {
    for(let i = 0; i < matrix.length; i++) {
        for(let j = 0; j < matrix[i].length; j++) {
            if(matrix[i][j] === target) return true;
        }
    }
    return false;
 };

Bunda biz matritsani har bir elementini berilgan targetga teng yoki teng emasligini tekshirish uchun ichma-ich for sikllaridan foydalanyapmiz. Bu algoritmning hisoblash vaqti O(m*n), m - matritsaning qatorlar soni, n - matritsaning ustunlari soni. Aslida, keraksiz ishni amalga oshiryapmiz. Bizga matritsa elementlari ma'lum bir tartibda saralangani haqidagi ma'lumotdan foydalanmayapmiz, ya'ni keraksiz ishni bajaryabmiz.
Matritsaning elementlari ma'lum bir qoida asosida saralangani haqidagi ma'lumotni inobatga olib, biz quyidagi yechimni berishimiz mumkin:

function searchMatrix(matrix, target) {
  const numRows = matrix.length;
  const numCols = matrix[0].length;
  let left = 0;
  let right = numRows * numCols - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midElement = matrix[Math.floor(mid / numCols)][mid % numCols];

    if (midElement === target) {
      return true;
    } else if (midElement < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
}

Ma'lumki, saralangan massivdan biror-bir elementni topish uchun "Binary search" algoritmidan foydalanish samaralidir. Ushbu yondashuvda element har doim massivning o'rtasidan qidiriladi. Bizda matritsa bo'lganligi uchun matritsaning o'rta elementini topish hisob-kitoblarimiz biroz boshqacharoq bo'ladi. Agar matritsaning o'rta elementi qidirilayotgan elementdan kichik bo'lsa bizga matritsaning o'rta elementidan chap qismi kerak emas, ularni tashlab yuborsak bo'ladi. Agar matritsaning o'rta elementi qidirilayotgan elementdan katta bo'lsa bizga matritsaning o'rta elementidan o'ng qismi kerak emas, ularni tashlab yuborsak bo'ladi. Shunday yo'l bilan biz matritsadan ma'lum bir elementni qidirishni optimallashtirdik. Bunda algoritm hisoblanishiga ketadigan vaqt O(log(m*n)).

Duplicated work - takroriy ish. Algoritmda biror-bir ishni takroran bajaryapmizmi?

Masala:
n-chi fibonacci sonini qaytaring.

Yechim:

function fibonacci(n) {
    if (n <= 1) {
        return n;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Ushbu funksiya fibonacci sonlar ketma-ketligidan n-sonni qaytaradi. Bu sonlar ketma-ketligi - har bir raqam oldingi ikkitasining yig'indisi bo'lgan raqamlar qatoridir. U 0 va 1 dan boshlanadi va keyingi raqamlar oldingi ikkita raqamni qo'shish orqali hosil bo'ladi. Masalan:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Biroq, buni amalga oshirishda, funktsiya bir xil fibonacci raqamlarini bir necha marta qayta-qayta hisoblab chiqadi, ya'ni takroriy ishni bajaryapmiz. Algoritm hisoblanishiga ketadigan vaqt O(2^n). Uni qanday optimallashtirishimiz mumkin?

Biz qo'shimcha xotiradan foydalanishimiz mumkin:

function fibonacci(n) {
    let memo = {};
    return fibonacciHelper(n, memo);
}

function fibonacciHelper(n, memo) {
    if (n <= 1) {
        return n;
    }

    if (memo[n]) {
        return memo[n];
    }

    memo[n] = fibonacciHelper(n - 1, memo) + fibonacciHelper(n - 2, memo);
    return memo[n];
}

fibonacciHelper funksiyasi argument sifatida n va memoni qabul qiluvchi rekursiv yordamchi funksiyadir. fibonacciHelper funktsiyasi ichida biz berilgan n uchun fibonacci raqami memo ob'ektida mavjudligini tekshiramiz. Agar u mavjud bo'lsa, biz memo ob'ektidan oldindan hisoblangan qiymatni qaytaramiz. Agar fibonacci raqami memo ob'ektida mavjud bo'lmasa, u fibonacci raqamini rekursiv hisoblab chiqadi. Hisoblangan fibonacci raqami keyinchalik ma'lumot sifatida memo ob'ektida saqlanadi va qaytariladi.
Qo'shimcha xotiradan foydalangan holda oldindan hisoblangan fibonacci raqamlarini saqlash orqali takroriy ishlarni oldini olamiz. Bu fibonacci hisobining samaradorligini sezilarli darajada yaxshilaydi. Algoritm hisoblanishiga ketadigan vaqt O(n). Bu yaxshilanishga avvaldan hisoblangan fibonacci raqamlarini saqlash yordamida ortiqcha hisob-kitoblarni yo‘q qilish orqali erishildi.

Xulosa:

BUD optimallashtirish usuli - "to'siqlar, keraksiz ish va takroriy ish" degan ma'noni anglatadi va algoritmlar yoki kodlardagi samarasizlikni aniqlash va bartaraf etish uchun ishlatiladigan printsipdir. Ushbu usul "Brute Force" yechimini ishlab chiqqandan keyingi birinchi variantlardan biri bo'lishi kerak. Chunki u algoritmning hisoblash vaqtini yaxshilash usullarini aniqlashga qaratilgandir.

"Big O" haqida gaplashamiz

Dilbar — Wed, 05 Jul 2023 05:03:04 +0000

Big O - nima?

Big O - bu yozilgan algoritm qanchalik samaradorligini aniqlovchi o'lchov. Bu o'lchov algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon qanday o'zgarishini taqribiy ko'rsatadi.

O(1) - algoritmga kiruvchi qiymatlar o'sib borsa ham, algoritm hisoblanishiga ketadigan vaqt yoki maydon o'zgarmasdan qolishini anglatadi.

function addValues(a, b) {
  return a + b;
}

Ushbu addValues funksiyasi a va b o'zgaruvchilarini kiruvchi qiymatlar sifatida oladi va ularning yig'indisini qaytaradi. a va b o'zgaruvchilarining qiymati ortib borishi algoritm hisoblanishiga ketadigan vaqtga hech qanday ta'sir qilmaydi. Shuning uchun ushbu algoritm hisoblanishiga O(1) vaqt talab qilinadi, hech qanday qo'shimcha joy ishlatilinmaganligi sababli algoritm talab qiladigan joy ham O(1).

O(n) - algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon ham birdek o'sib borishini anglatadi.
Masalan: Agar biz algoritmda n o'lchamdagi massiv yaratsak, algoritm O(n) joy talab qiladi.

function calculateSum(a) {
  let sum = 0;
  for (const value of a) {
    sum += value;
  }
  return sum;
}

Ushbu algoritm a massiv elementlarining yig'indisini qaytaradi. Massiv uzunligini n deb belgilab oladigan bo'lsak, n oshib borgani sari algoritm hisoblanishiga ketadigan vaqt - massivning har bir elementini sum o'zgaruvchisiga qo'shish kerakligi sababli, u ham birdek oshib boradi. Shuning uchun, algoritm hisoblanishiga ketadigan vaqt O(n). Talab qilinadigan maydon esa faqat sum o'zgaruvchisi e'lon qilinganligi sababli O(1).

O(log(n)) - algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon logarifmik ravishda o'sadi.

function powersOf2(n) {
  if (n < 1) {
    return 0;
  } else if (n === 1) {
    console.log(1);
    return 1;
  } else {
    let prev = powersOf2(Math.floor(n / 2));
    let curr = prev * 2;
    console.log(curr);
    return curr;
  }
}

Berilgan funksiya powersOf2 berilgan n sonigacha bo‘lgan 2 ning darajalarini hisoblab chiqadi va chop etadi. Rekursiv ravishda n ni yarmiga bo'lish va har bir qadamda 2 ning oldingi darajasini 2 ga ko'paytirish orqali funktsiya n ning berilgan qiymatiga qadar 2 ning darajasini hosil qiladi va chop etadi. Masalan: n = 4 bo'lganida funksiya quyidagicha ishlaydi:

powersOf2(4)
  -> powersOf2(2)
    -> powersOf2(1)
      -> chop etish va 1 ni qaytarish
    -> chop etish va 2 ni qaytarish
  -> chop etish va 4 ni qaytarish

n = 4 => n = 2^2 bo'lganida, funksiya 2 marta,
n = 8 => n = 2^3 bo'lganida, funksiya 3 marta,
n = 16 => n = 2^4 bo'lganida, funksiya 4 marta chaqirilyapti. Har 2 ning darajalarida funksiya 1ta ko'p chaqiriladi. Tenglikni ikkala tarafini logarifmlab yuborsak, kutgan natijamizga erishamiz:
n = 4 => log(n) = log(2^2) => log(n) = 2
Demak, algoritm hisoblanishiga ketadigan vaqt O(log(n)) ekan. Algoritm hisoblanishiga ketadigan maydon ham funksiya har chaqirilganida avvalgi funksiya qaytargan qiymatni saqlab turishiga joy olganligi sababli O(log(n)).

Algoritmga kiruvchi elementlar soni har safar algoritm ishga tushganida ikki baravar kamayadigan bo'lsa, bu algoritm hisoblanishiga ketadigan vaqt O(log(n)) bo'lishi mumkin.

O(2^n) - algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon eksponensial ravishda ortib boradi.

function fibonacci(n) {
  if (n <= 0) return 0;
  else if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Berilgan funksiya fibonacci sonlar ketma-ketligidan n-sonni qaytaradi. Bu sonlar ketma-ketligi - har bir raqam oldingi ikkitasining yig'indisi bo'lgan raqamlar qatoridir. U 0 va 1 dan boshlanadi va keyingi raqamlar oldingi ikkita raqamni qo'shish orqali hosil bo'ladi. Masalan:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
n = 4 bo'lganida funksiya quyidagicha ishlaydi:

                             fibonacci(4)
                             /          \
                      fibonacci(3)   fibonacci(2)
                     /  \                     /  \
          fibonacci(2)  fibonacci(1) fibonacci(1) fibonacci(0)
             / \
   fibonacci(1) fibonacci(0)

n = 1 bo'lganida, funksiya 1 marta,
n = 2 bo'lganida, funksiya 3 marta,
n = 3 bo'lganida, funksiya 5 marta,
n = 4 bo'lganida, funksiya 9 marta,
n = 5 bo'lganida, funksiya 15 marta,
n = 6 bo'lganida, funksiya 25 marta chaqirilyapti.
Funksiya chaqiruvlari eksponensial o'sib bormoqda. U deyarlik O((1.6)^n) ga yaqin. 1.6 sonini taqriban 2 ga teng deb olib, algoritm hisoblanishiga ketadigan vaqtni O(2^n) deb olishimiz mumkin.

Big O qoidalari

O'zgarmaslarni tushirib qoldirish
O(n + n) = O(2*n) - quyidagicha vaqt talab qiluvchi algoritm aslida O(n). Bu yerdagi 2 soni o'zgarmas, ya'ni algoritmga kiruvchi qiymat ortib boragni sari u o'zgarmaydi. Shuning uchun uni bemalol tushirib qoldirish mumkin.

Dominant bo'lmaganlarini tushirib qoldirish
O(n^2 + n ^2) = O(2 * n^2) - bundan 2 ni, ya'ni bitta n^2 ni tushirib qoldirishimiz mumkin (o'zgarmaslarni tushirib qoldirish qoidasiga ko'ra).
O(n^2 + n) - bu ifodadachi? Avvalgi ifodada bemalol bitta n^2 ni tushirib qoldirgan bo'lsak, bunisida n ni ham tushirib qoldirishimiz mumkin. Chunki, u algoritmga kiruvchi qiymat oshib borgani sari n^2 chalik oshmaydi, uning o'zgarishi deyarli sezilarsiz.

Ko'p qismli algoritmlar

Algoritm bir nechta qismli bo'lishi mumkin. Masalan, quyidagi algoritm 2 o'zgaruvchini oladi (a va b massivlarini) va ular ustida ishlaydi:

function printElements(a, b) {
  for (const aValue of a) {
    console.log(aValue);
  }
  for (const bValue of b) {
    console.log(bValue);
  }
}

Ushbu algoritmning hisoblanishiga ketadigan vaqtni aytishga shoshilmang. Birinchi for sikli a massiv uzunligi - A bo'yicha, ikkinchi for sikli b massiv uzunligi - B bo'yicha vaqt sarflaydi. Avval a massiviga, keyin b massiviga murojaat qilinmoqda. Shuning uchun, bu yerda algoritm hisoblash vaqtlari qo'shiladi: O(A + B).

function printElements(a, b) {
  for (const aValue of a) {
    for (const bValue of b) {
      console.log(aValue, ' , ', bValue);
    }
  }
}

Ushbu algoritmda esa hisoblash vaqtlari ko'paytiriladi: O(A*B). Buning sababi, har bir a massivi elementi uchun butun b massiv elementlariga murojaat qilinmoqda.

Xulosa:

Xulosa qilib aytganda, Big O algoritmlarning samaradorligini tahlil qilish uchun qimmatli vositadir. U algoritmning vaqt yoki maydon talablarini kiruvchi qiymatlar bilan qanday o'lchashni ifodalashning standartlashtirilgan usulini taqdim etadi. Algoritmning Big O murakkabligini tushunib, biz uning ishlash xususiyatlarini baholashimiz va algoritmlarni tanlash yoki optimallashtirishda asosli qarorlar qabul qilishimiz mumkin.

Nega dasturchi uchun muloqot qilish qobiliyati bo’lishi muhim?

Dilbar — Tue, 04 Jul 2023 08:56:30 +0000

بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم

Dasturchilarda asosan muloqot qila olish qobiliyati kam bo’ladi. Chunki ular insonlar muammolarini hal qiladigan dasturlarni ishlab chiqish, ya’ni asosan kod yozish bilan shug’ullanishadi. Xo’sh, nega unda dasturchilar biror joyga ishga topshirganlarida ularni ishga olishni hal qilishda ularning muloqot qila olish qobiliyatlariga ham qarashadi?

Buning bir necha sabablari bor:

Dasturchilar ko’p hollarda jamoada ishlashadi. Jamoada turli fe’l-atvorli odamlar bilan ishlashga to’g’ri keladi. Ular bilan til topisha olish, bir-birini tushunib ishlash uchun albatta muloqot qilish qobiliyatlari muhim!
Dasturchi qanday muammoni hal qilishi kerakligi, dasturning talablari va maqsadlarini to’g’ri tushunib olishi kerak. Buning uchun ham muloqot qilish qobiliyatlari muhim. Dasturda nimalar bo’lishi kerakligi haqidagi tavsilotlarni to’g’ri savollar berib, so’rab bilib olish dasturchining mahorati sanaladi. Shunda keyinchalik kelib chiqishi mumkin bo’lgan tushunmovchiliklar bo’lishining ehtimolini kamaytirish, dastur tezroq muddatda hamda muvaffaqiyatli yakunlanishi imkoniyatini oshirish mumkin bo’ladi.
Ba’zan mijoz bilan bevosita gaplashishga to’g’ri kelishi mumkin. O’sha paytda muloqot qilish qobiliyati qanchalik muhimligi bilinadi. Bunda texnik va texnik bo’lmagan nutq o’rtasidagi farqni bilish zarurdir. Chunki qanday turdagi mijoz bilan muloqot qilinishini bilib bo’lmaydi, mijozga o’zini tilida tushunarli muloqot qilish muhimdir.
Samarali muloqot qilish qobiliyati boshqa dasturchilar bilan keng aloqalarni o’rnatishga, sohadagi eng soʻnggi texnologiyalar, oxirgi yangiliklar, qiziqarli loyihalar va turli ish imkoniyatlari haqida maʼlumotlarni olishga yordam beradi. Shu bilan birga ishga oluvchilar bilan samarali munosabatlarni rivojlantirishga xizmat qiladi, bu esa ular tomonidan ishga tavsiyanomalar olinishiga olib kelishi mumkin.

Xulosa:

Yuqorida keltirilgan bir nechta sabablardan ko’rinib turibdiki, hozirgi kunda dasturchilar uchun samarali muloqot qilish qobiliyatlarini o’zlarining texnik ko’nikmalari bilan birga o’stirib borishlari talab darajasiga aylanib ulgurgan. Dasturchi sifatida yaxshiroq va samaraliroq muloqot qilish uchun faol tinglashni ham bilish juda zarurdir.