Các bài lưu

TTUD60TH-BT: Lời giải bài PHẦN-THƯỞNG

09/01/2022 lời giải, mã nguồn 1 bình luận

Dưới đây là lời giải bài PHẦN-THƯỞNG trong các bài thực hành mở của môn Thuật Toán Ứng Dụng.

Chú ý rằng đây chỉ là lời giải của một trong những bạn đã đạt 100% điểm, không phải là bài giải mẫu của người ra đề.

#include<iostream>
#include<vector>
using namespace std;

struct canh {
    int a, b, t;
};

int n, m, vc = 1000000000, duongdi[1001], V[1001];

long long phanthuong[10001];

vector <canh> E;

void khoitao() {
    duongdi[1] = 0;
    phanthuong[1] = V[1];
    for (int i = 2; i <= n; i++) {
        duongdi[i] = vc;
        phanthuong[i] = 0;
    }
}

void dichuyen() {
    for (int e = 0; e < E.size(); e++)
        for (int i = 0; i < E.size(); i++)
            if (duongdi[E[i].a] != vc) {
                if (duongdi[E[i].b] > (duongdi[E[i].a] + E[i].t))
                    phanthuong[E[i].b] = phanthuong[E[i].a] + V[E[i].b];
                if (duongdi[E[i].b] == (duongdi[E[i].a] + E[i].t))
                    phanthuong[E[i].b] = max(phanthuong[E[i].b], (phanthuong[E[i].a] + V[E[i].b]));
                duongdi[E[i].b] = min(duongdi[E[i].b], duongdi[E[i].a] + E[i].t);
            }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> V[i];
    cin >> m;
    for (int i = 0; i < m; i++) {
        int p, q, t;
        cin >> p >> q >> t;
        canh temp = { p, q, t };
        E.push_back(temp);
        temp = { q, p, t };
        E.push_back(temp);
    }

    khoitao();
    dichuyen();
    if (duongdi[n] == vc) cout << 0;
    else cout << phanthuong[n];
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

#include<iostream>

#include<vector>

using namespace std;

struct canh {

int a, b, t;

};

int n, m, vc = 1000000000, duongdi[1001], V[1001];

long long phanthuong[10001];

vector <canh> E;

void khoitao() {

duongdi[1] = 0;

phanthuong[1] = V[1];

for (int i = 2; i <= n; i++) {

duongdi[i] = vc;

phanthuong[i] = 0;

}

}

void dichuyen() {

for (int e = 0; e < E.size(); e++)

for (int i = 0; i < E.size(); i++)

if (duongdi[E[i].a] != vc) {

if (duongdi[E[i].b] > (duongdi[E[i].a] + E[i].t))

phanthuong[E[i].b] = phanthuong[E[i].a] + V[E[i].b];

if (duongdi[E[i].b] == (duongdi[E[i].a] + E[i].t))

phanthuong[E[i].b] = max(phanthuong[E[i].b], (phanthuong[E[i].a] + V[E[i].b]));

duongdi[E[i].b] = min(duongdi[E[i].b], duongdi[E[i].a] + E[i].t);

}

}

int main() {

cin >> n;

for (int i = 1; i <= n; i++) cin >> V[i];

cin >> m;

for (int i = 0; i < m; i++) {

int p, q, t;

cin >> p >> q >> t;

canh temp = { p, q, t };

E.push_back(temp);

temp = { q, p, t };

E.push_back(temp);

}

khoitao();

dichuyen();

if (duongdi[n] == vc) cout << 0;

else cout << phanthuong[n];

}

Đọc tiếp...

Game-K58-TH, bài 7: Unity Networking

23/07/2020 lý thuyết, mã nguồn Chưa có bình luận

Các nội dung chính trong buổi này:

Multiplayer game
Multiplayer flow
Networking
Multiplayer game trong unity
Game Pong, phiên bản mạng

Đọc tiếp...

Game-K58-TH, bài 6: Clone Game Kinh Điển Tetris

23/07/2020 lý thuyết, mã nguồn Chưa có bình luận

Các nội dung chính trong buổi này:

Gameplay
Chuẩn bị tài nguyên
Thiết lập project và các thành phần
Cấu trúc dữ liệu chính
Xử lý sự kiện
Các loại biến cố trong trò chơi
Các mở rộng nên xem xét

Đọc tiếp...

Game-K58-TH, bài 5: Game 2D Đơn Giản

07/06/2020 lý thuyết, mã nguồn Chưa có bình luận

Các nội dung chính trong buổi này:

Xây dựng kịch bản
Chuẩn bị tài nguyên
Thiết lập project và các thành phần
Xây dựng màn hình trò chơi
Xây dựng hành động cho nhân vật chính
Xây dựng hành động cho máy
Xử lý biến cố
Bổ sung các chi tiết khác
Bài tập

Đọc tiếp...

Game-K58-PM, bài 7: Unity networking

25/09/2019 lý thuyết, mã nguồn Chưa có bình luận

Các nội dung chính trong buổi này:

Multiplayer game
Multiplayer flow
Networking
Multiplayer game trong unity
Game Pong, phiên bản mạng

Đọc tiếp...

Game-K58-PM, bài 6: Clone game kinh điển Tetris

23/09/2019 lý thuyết, mã nguồn Chưa có bình luận

Các nội dung chính trong buổi này:

Gameplay
Chuẩn bị tài nguyên
Thiết lập project và các thành phần
Cấu trúc dữ liệu chính
Xử lý sự kiện
Các loại biến cố trong trò chơi
Các mở rộng nên xem xét

Đọc tiếp...

Game-K58-PM, bài 5: Game 2D đơn giản

12/09/2019 lý thuyết, mã nguồn Chưa có bình luận

Các nội dung chính trong buổi này:

Xây dựng kịch bản
Chuẩn bị tài nguyên
Thiết lập project và các thành phần
Xây dựng màn hình trò chơi
Xây dựng hành động cho nhân vật chính
Xây dựng hành động cho máy
Xử lý biến cố
Bổ sung các chi tiết khác
Bài tập

Đọc tiếp...

CTD Bài 11-A: Mã C# minh họa cho thuật toán CYK

24/11/2016 mã nguồn Chưa có bình luận

using System;
using System.Collections.Generic;

class Rule {
    public char left;
    public string right;
    public Rule(char l, string r) {
        left = l; right = r;
    }
    public string ToFineString() {
        string s = left + " -->";
        for (int i = 0; i < right.Length; i++)
            s += " " + right[i];
        return s;
    }
}

class PTCYK {
    public List<Rule> rules = new List<Rule>();
    string[,] table = null;
    string w = null;
    int n = 0;

    // thêm luật left --> right vào tập luật
    public void AddRule(char left, string right) {
        rules.Add(new Rule(left, right));
    }

    public void PrintAllRules() {
        Console.WriteLine("<bo luat van pham>");
        foreach (Rule r in rules)
            Console.WriteLine("  " + r.ToFineString());
        Console.WriteLine();
    }

    void InitData(string x) {
        w = x;
        n = x.Length;
        table = new string[n+1, n+1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) table[i,j] = "";
    }

    void FirstProcess() {
        for (int i = 1; i <= n; i++)
            foreach (Rule r in rules)
                if (r.right.Length == 1)
                    if (w[i-1] == r.right[0]) table[i,1] += r.left;
    }

    bool IsIn(char x, string w) {
        return w.IndexOf(x) != -1;
    }
    
    bool CanGen(int j, int i, Rule r) {
        for (int k = 1; k <= j-1; k++)
            if (IsIn(r.right[0], table[i,k]))
                if (IsIn(r.right[1], table[i+k, j-k]))
                    return true;
        return false;
    }
    
    void GenTable() {
        for (int j = 2; j <= n; j++)
            for (int i = 1; i <= n-j+1; i++)
                foreach (Rule r in rules)
                    if (r.right.Length == 2)
                        if (!IsIn(r.left, table[i,j]))
                            if (CanGen(j, i, r)) table[i,j] += r.left;
    }
    
    public void Process(string x) {
        InitData(x);
        FirstProcess();
        GenTable();
    }
    
    public void PrintResult() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) Console.Write("[{0,5}]", table[j,n+1-i]);
            Console.WriteLine();
        }
    }
}
class Program {
    public static void Main() {
        PTCYK parser = new PTCYK();
        // nạp bộ luật vào bộ phân tích
        parser.AddRule('S', "AB");
        parser.AddRule('S', "XB");
        parser.AddRule('T', "AB");
        parser.AddRule('T', "XB");
        parser.AddRule('X', "AT");
        parser.AddRule('A', "a");
        parser.AddRule('B', "b");
        parser.PrintAllRules();
        // phân tích thử
        string w = "aaabbb";
        parser.Process(w);
        // in ra bảng CYK
        Console.WriteLine("Bang phan tich CYK cho day \"{0}\"\n", w);
        parser.PrintResult();
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

using System;

using System.Collections.Generic;

class Rule {

public char left;

public string right;

public Rule(char l, string r) {

left = l; right = r;

}

public string ToFineString() {

string s = left + " -->";

for (int i = 0; i < right.Length; i++)

s += " " + right[i];

return s;

}

}

class PTCYK {

public List<Rule> rules = new List<Rule>();

string[,] table = null;

string w = null;

int n = 0;

// thêm luật left --> right vào tập luật

public void AddRule(char left, string right) {

rules.Add(new Rule(left, right));

}

public void PrintAllRules() {

Console.WriteLine("<bo luat van pham>");

foreach (Rule r in rules)

Console.WriteLine(" " + r.ToFineString());

Console.WriteLine();

}

void InitData(string x) {

w = x;

n = x.Length;

table = new string[n+1, n+1];

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++) table[i,j] = "";

}

void FirstProcess() {

for (int i = 1; i <= n; i++)

foreach (Rule r in rules)

if (r.right.Length == 1)

if (w[i-1] == r.right[0]) table[i,1] += r.left;

}

bool IsIn(char x, string w) {

return w.IndexOf(x) != -1;

}

bool CanGen(int j, int i, Rule r) {

for (int k = 1; k <= j-1; k++)

if (IsIn(r.right[0], table[i,k]))

if (IsIn(r.right[1], table[i+k, j-k]))

return true;

return false;

}

void GenTable() {

for (int j = 2; j <= n; j++)

for (int i = 1; i <= n-j+1; i++)

foreach (Rule r in rules)

if (r.right.Length == 2)

if (!IsIn(r.left, table[i,j]))

if (CanGen(j, i, r)) table[i,j] += r.left;

}

public void Process(string x) {

InitData(x);

FirstProcess();

GenTable();

}

public void PrintResult() {

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) Console.Write("[{0,5}]", table[j,n+1-i]);

Console.WriteLine();

}

}

}

class Program {

public static void Main() {

PTCYK parser = new PTCYK();

// nạp bộ luật vào bộ phân tích

parser.AddRule('S', "AB");

parser.AddRule('S', "XB");

parser.AddRule('T', "AB");

parser.AddRule('T', "XB");

parser.AddRule('X', "AT");

parser.AddRule('A', "a");

parser.AddRule('B', "b");

parser.PrintAllRules();

// phân tích thử

string w = "aaabbb";

parser.Process(w);

// in ra bảng CYK

Console.WriteLine("Bang phan tich CYK cho day \"{0}\"\n", w);

parser.PrintResult();

}

}

Đọc tiếp...

Mã nguồn: thuật toán CYK bằng C#

07/05/2015 mã nguồn Chưa có bình luận

using System;
using System.Collections.Generic;

class Rule {
    public char left;
    public string right;
    public Rule(char l, string r) {
        left = l; right = r;
    }
    public string ToFineString() {
        string s = left + " -->";
        for (int i = 0; i < right.Length; i++)
            s += " " + right[i];
        return s;
    }
}

class PTCYK {
    public List<Rule> rules = new List<Rule>();
    string[,] table = null;
    string w = null;
    int n = 0;

    // thêm luật left --> right vào tập luật
    public void AddRule(char left, string right) {
        rules.Add(new Rule(left, right));
    }

    public void PrintAllRules() {
        Console.WriteLine("<bo luat van pham>");
        foreach (Rule r in rules)
            Console.WriteLine("  " + r.ToFineString());
        Console.WriteLine();
    }

    void InitData(string x) {
        w = x;
        n = x.Length;
        table = new string[n+1, n+1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) table[i,j] = "";
    }

    void FirstProcess() {
        for (int i = 1; i <= n; i++)
            foreach (Rule r in rules)
                if (r.right.Length == 1)
                    if (w[i-1] == r.right[0]) table[i,1] += r.left;
    }

    bool IsIn(char x, string w) {
        return w.IndexOf(x) != -1;
    }
    
    bool CanGen(int j, int i, Rule r) {
        for (int k = 1; k <= j-1; k++)
            if (IsIn(r.right[0], table[i,k]))
                if (IsIn(r.right[1], table[i+k, j-k]))
                    return true;
        return false;
    }
    
    void GenTable() {
        for (int j = 2; j <= n; j++)
            for (int i = 1; i <= n-j+1; i++)
                foreach (Rule r in rules)
                    if (r.right.Length == 2)
                        if (!IsIn(r.left, table[i,j]))
                            if (CanGen(j, i, r)) table[i,j] += r.left;
    }
    
	public void Process(string x) {
        InitData(x);
        FirstProcess();
        GenTable();
	}
    
    public void PrintResult() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) Console.Write("[{0,5}]", table[j,n+1-i]);
            Console.WriteLine();
        }
    }
}
class Program {
    public static void Main() {
        PTCYK parser = new PTCYK();
        // nạp bộ luật vào bộ phân tích
        parser.AddRule('S', "AB");
        parser.AddRule('S', "XB");
        parser.AddRule('T', "AB");
        parser.AddRule('T', "XB");
        parser.AddRule('X', "AT");
        parser.AddRule('A', "a");
        parser.AddRule('B', "b");
        parser.PrintAllRules();
        // phân tích thử
        parser.Process("aaabbb");
        // in ra bảng CYK
        parser.PrintResult();
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

using System;

using System.Collections.Generic;

class Rule {

public char left;

public string right;

public Rule(char l, string r) {

left = l; right = r;

}

public string ToFineString() {

string s = left + " -->";

for (int i = 0; i < right.Length; i++)

s += " " + right[i];

return s;

}

}

class PTCYK {

public List<Rule> rules = new List<Rule>();

string[,] table = null;

string w = null;

int n = 0;

// thêm luật left --> right vào tập luật

public void AddRule(char left, string right) {

rules.Add(new Rule(left, right));

}

public void PrintAllRules() {

Console.WriteLine("<bo luat van pham>");

foreach (Rule r in rules)

Console.WriteLine(" " + r.ToFineString());

Console.WriteLine();

}

void InitData(string x) {

w = x;

n = x.Length;

table = new string[n+1, n+1];

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++) table[i,j] = "";

}

void FirstProcess() {

for (int i = 1; i <= n; i++)

foreach (Rule r in rules)

if (r.right.Length == 1)

if (w[i-1] == r.right[0]) table[i,1] += r.left;

}

bool IsIn(char x, string w) {

return w.IndexOf(x) != -1;

}

bool CanGen(int j, int i, Rule r) {

for (int k = 1; k <= j-1; k++)

if (IsIn(r.right[0], table[i,k]))

if (IsIn(r.right[1], table[i+k, j-k]))

return true;

return false;

}

void GenTable() {

for (int j = 2; j <= n; j++)

for (int i = 1; i <= n-j+1; i++)

foreach (Rule r in rules)

if (r.right.Length == 2)

if (!IsIn(r.left, table[i,j]))

if (CanGen(j, i, r)) table[i,j] += r.left;

}

public void Process(string x) {

InitData(x);

FirstProcess();

GenTable();

}

public void PrintResult() {

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) Console.Write("[{0,5}]", table[j,n+1-i]);

Console.WriteLine();

}

}

}

class Program {

public static void Main() {

PTCYK parser = new PTCYK();

// nạp bộ luật vào bộ phân tích

parser.AddRule('S', "AB");

parser.AddRule('S', "XB");

parser.AddRule('T', "AB");

parser.AddRule('T', "XB");

parser.AddRule('X', "AT");

parser.AddRule('A', "a");

parser.AddRule('B', "b");

parser.PrintAllRules();

// phân tích thử

parser.Process("aaabbb");

// in ra bảng CYK

parser.PrintResult();

}

}

Đọc tiếp...

Mã nguồn: thuật toán phân tích top-down bằng C#

14/04/2015 mã nguồn Chưa có bình luận

using System;
using System.Collections.Generic;

class Rule {
    public char left;
    public string right;
    public Rule(char l, string r) {
        left = l; right = r;
    }
    public string ToFineString() {
        string s = left + " -->";
        for (int i = 0; i < right.Length; i++)
            s += " " + right[i];
        return s;
    }
}
class Step {
    public int ruleNumber, position;
    public Step(int r, int p) {
        ruleNumber = r; position = p;
    }
}
class PTTD {
    public List rules = new List();
    public List steps;
    string w = null;

    // thêm luật left --> right vào tập luật
    public void AddRule(char left, string right) {
        rules.Add(new Rule(left, right));
    }

    public void PrintAllRules() {
        Console.WriteLine("");
        foreach (Rule r in rules)
            Console.WriteLine("  " + r.ToFineString());
        Console.WriteLine();
    }

    public void PrintSteps2() {
        string w = "S";
        Console.Write("S");
        foreach (Step s in steps) {
            string w0 = DoStep(w, s);
            Console.Write(" => {0}", w0);
            w = w0;
        }
        Console.WriteLine();
    }
	
    string DoStep(string w, Step s) {
        string w1 = w.Substring(0, s.position);
        string w2 = w.Substring(s.position + 1);
        return w1 + rules[s.ruleNumber].right + w2;
    }

    // tìm kí hiệu không kết thúc đầu tiên trong s
    public int FindNonterminal(string s) {
        for (int i = 0; i < s.Length; i++) {
            if (i >= w.Length) return i;
            if (s[i] != w[i]) return i;
        }
        return -1;
    }

    public bool Try(string s) {
        if (s == w) return true;
        int n = FindNonterminal(s);
        if (n != -1)
            for (int i = 0; i < rules.Count; i++)
                if (rules[i].left == s[n]) {
                    Step st = new Step(i, n);
                    steps.Add(st);
                    PrintSteps2();
                    if (Try(DoStep(s, st))) return true;
                    steps.RemoveAt(steps.Count - 1);
                    PrintSteps2();
                }
        return false;
    }

    public bool Process(string x) {
        steps = new List();
        w = x;
        return Try("S");
    }
}
class Program {
    public static void Main() {
        PTTD parser = new PTTD();
        parser.AddRule('S', "E");
        parser.AddRule('E', "Te");
        parser.AddRule('e', "&Te");
        parser.AddRule('e', "");
        parser.AddRule('T', "Ft");
        parser.AddRule('t', "|Ft");
        parser.AddRule('t', "");
        parser.AddRule('F', "~F");
        parser.AddRule('F', "(E)");
        parser.AddRule('F', "d");
        parser.AddRule('F', "s");
        parser.PrintAllRules();
        if (parser.Process("d&~s"))
            Console.WriteLine("\nThuat toan ket thuc thanh cong");
        else
            Console.WriteLine("\nThuat toan ket thuc that bai");
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

using System;

using System.Collections.Generic;

class Rule {

public char left;

public string right;

public Rule(char l, string r) {

left = l; right = r;

}

public string ToFineString() {

string s = left + " -->";

for (int i = 0; i < right.Length; i++)

s += " " + right[i];

return s;

}

}

class Step {

public int ruleNumber, position;

public Step(int r, int p) {

ruleNumber = r; position = p;

}

}

class PTTD {

public List rules = new List();

public List steps;

string w = null;

// thêm luật left --> right vào tập luật

public void AddRule(char left, string right) {

rules.Add(new Rule(left, right));

}

public void PrintAllRules() {

Console.WriteLine("");

foreach (Rule r in rules)

Console.WriteLine(" " + r.ToFineString());

Console.WriteLine();

}

public void PrintSteps2() {

string w = "S";

Console.Write("S");

foreach (Step s in steps) {

string w0 = DoStep(w, s);

Console.Write(" => {0}", w0);

w = w0;

}

Console.WriteLine();

}

string DoStep(string w, Step s) {

string w1 = w.Substring(0, s.position);

string w2 = w.Substring(s.position + 1);

return w1 + rules[s.ruleNumber].right + w2;

}

// tìm kí hiệu không kết thúc đầu tiên trong s

public int FindNonterminal(string s) {

for (int i = 0; i < s.Length; i++) {

if (i >= w.Length) return i;

if (s[i] != w[i]) return i;

}

return -1;

}

public bool Try(string s) {

if (s == w) return true;

int n = FindNonterminal(s);

if (n != -1)

for (int i = 0; i < rules.Count; i++)

if (rules[i].left == s[n]) {

Step st = new Step(i, n);

steps.Add(st);

PrintSteps2();

if (Try(DoStep(s, st))) return true;

steps.RemoveAt(steps.Count - 1);

PrintSteps2();

}

return false;

}

public bool Process(string x) {

steps = new List();

w = x;

return Try("S");

}

}

class Program {

public static void Main() {

PTTD parser = new PTTD();

parser.AddRule('S', "E");

parser.AddRule('E', "Te");

parser.AddRule('e', "&Te");

parser.AddRule('e', "");

parser.AddRule('T', "Ft");

parser.AddRule('t', "|Ft");

parser.AddRule('t', "");

parser.AddRule('F', "~F");

parser.AddRule('F', "(E)");

parser.AddRule('F', "d");

parser.AddRule('F', "s");

parser.PrintAllRules();

if (parser.Process("d&~s"))

Console.WriteLine("\nThuat toan ket thuc thanh cong");

else

Console.WriteLine("\nThuat toan ket thuc that bai");

}

}

Đọc tiếp...