[8-Kittiamorn] ฝึกทำโจทย์ Data Structures and Algorithms – Recursion/Array/Stack/Queue/Linked Lists

** รายละเอียดของโค้ดแบบลึก ๆ จะอธิบายอยู่ในคลิปของแต่ละข้อ **

P-5.34 Caesar Cipher

Write a program that can perform the Caesar cipher for English messages
that include both upper- and lowercase characters

Python Code

SYMBOLS = ‘ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz’

MAX_KEY_SIZE = len(SYMBOLS)

def getMode():

    while True:

        print(‘Do you wish to encrypt or decrypt a message?’)

        mode = input().lower()

        if mode in [‘encrypt’, ‘e’, ‘decrypt’, ‘d’]:

            return mode

        else:

            print(‘Enter either “encrypt” or “e” or “decrypt” or “d”.’)

def getMessage():

    print(‘Enter your message:’)

    return input()

def getKey():

    key = 0

    while True:

        print(‘Enter the key number (1-%s)’ % (MAX_KEY_SIZE))

        key = int(input())

        if (key >= 1 and key <= MAX_KEY_SIZE):

            return key

        

def getTranslatedMessage(mode, message, key):

    if mode[0] == ‘d’:

        key = -key

    translated = ”

    for symbol in message:

        symbolIndex = SYMBOLS.find(symbol)

        if symbolIndex == -1: # Symbol not found in SYMBOLS.

            # Just add this symbol without any change.

            translated += symbol

        else:

            # Encrypt or decrypt.

            symbolIndex += key

            if symbolIndex >= len(SYMBOLS):

                symbolIndex -= len(SYMBOLS)

            elif symbolIndex < 0:

                symbolIndex += len(SYMBOLS)

            translated += SYMBOLS[symbolIndex]

    return translated

mode = getMode()

message = getMessage()

key = getKey()

print(‘Your translated text is:’)

print(getTranslatedMessage(mode, message, key))

 

จากโค้ดด้านบนจะแสดงถึงการเข้ารหัสและถอดรหัสแบบซีซาร์

รหัสซีซาร์ (Caesar cipher) ในทางด้านวิทยาการเข้ารหัสลับ หรือเป็นที่รู้จักกันในชื่ออื่นว่า shift cipherCaesar’s code หรือ Caesar shift เป็นเทคนิคการเข้ารหัสที่ง่ายและแพร่หลายที่สุด โดยใช้หลักการแทนที่ตัวอักษร ซึ่งในแต่ละตัวอักษรที่อยู่ในข้อความจะถูกแทนที่ด้วยตัวอักษรที่อยู่ลำดับถัดไปตามจำนวนตัวอักษรที่แน่นอน อย่างเช่น แปลงตัวอักษรไป 3 ตัว อักษร “A” ก็จะถูกแทนที่ด้วยอักษร “D” การเข้ารหัสแบบดังกล่าวตั้งชื่อตามจูเลียส ซีซาร์ ซึ่งคิดค้นขึ้นเพื่อการติดต่อสื่อสารกับแม่ทัพนายกองของเขา

ขั้นตอนการเข้ารหัสซีซาร์มักจะใช้ร่วมกับการเข้ารหัสที่มีความซับซ้อนมากกว่า เนื่องจากรหัสซีซาร์ใช้หลักการแทนที่ตัวอักษรเดี่ยวที่มีความตายตัว ดังนั้น รหัสดังกล่าวจึงสามารถถอดออกมาได้ง่าย รวมไปถึงความจริงที่ว่า ในทางปฏิบัติแล้ว มักจะไม่ได้ช่วยในการรักษาความปลอดภัยของข้อความนั้นเลย

YouTube Preview Image

 

C-6.28 Modify the ArrayStack implementation

Modify the ArrayQueue implementation so that the queue’s capacity is
limited to maxlen elements, where maxlen is an optional parameter to the
constructor (that defaults to None). If enqueue is called when the queue
is at full capacity, throw a Full exception (defined similarly to Empty).

YouTube Preview Image

C-7.36 Delete a node a Doubly Linkes List

            (แปลงโจทย์นิดหน่อย)

Give a complete implementation of the positional list ADT using a doubly
linked list that does not include any sentinel nodes.

โค้ด C

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

struct Node
{
int data;
struct Node *next;
struct Node *prev;
};

void deleteNode(struct Node **head_ref, struct Node *del)
{
if(*head_ref == NULL || del == NULL)
return;

if(*head_ref == del)
*head_ref = del->next;

if(del->next != NULL)
del->next->prev = del->prev;

if(del->prev != NULL)
del->prev->next = del->next;

free(del);
return;
}

void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->prev = NULL;

new_node->next = (*head_ref);

if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

(*head_ref) = new_node;
}

void printList(struct Node *node)
{
while(node!=NULL)
{
printf(“%d “, node->data);
node = node->next;
}
}

int main()
{
struct Node* head = NULL;

push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);

printf(“\n Original Linked list “);
printList(head);

deleteNode(&head, head); /*delete first node*/
deleteNode(&head, head->next); /*delete middle node*/
deleteNode(&head, head->next); /*delete last node*/

/* Modified linked list will be NULL<-8->NULL */
printf(“\n Modified Linked list “);
printList(head);

getchar();
}

จากโค้ดด้านบนจะเห็นได้ว่าผมได้ทำการกำหนด linked list เอาไว้ในโค้ดแล้ว หลังจากนั้นจึงใช้ Function ต่างๆในโค้ดเพื่อทำการ Delete node ต่างๆ ใน linked list จนเหลือเป็น node สุดท้าย

YouTube Preview Image

 

R-7.6 Fast Linked List

Suppose that x and y are references to nodes of circularly linked lists,
although not necessarily the same list. Describe a fast algorithm for telling
if x and y belong to the same list.

YouTube Preview Image

 

 

  •  
  •  
  •  
  •  
  •  
  •  
KITTIAMORN CHUMAOM
at GlurGeek.Com
เป็นนักศึกษาคณะวิศวะกรรมศาสตร์สาขาคอมพิวเตอร์มหาวิทยาลัยกรุงเทพ
ชอบถ่ายภาพและชอบหาวิธีมองมุมใหม่ๆในการถ่ายภาพ และรักการฟังเพลงอย่างมาก
โดยเฉพาะเพลงแนว Blues และ Jazz

Leave a Reply