Khóa học C++ daynhauhoc.com

Khóa học này được anh em trên DAYNHAUHOC cùng nhau xây dựng cũng đã lâu và vẫn còn tiếp tục được phát triển.

dev210x-course_card_image-378x225

Nội dung trình bày, bố cục khá hợp lý dành cho những bạn mới bắt đầu với việc tiếp xúc các ngôn ngữ lập trình nói chung và ngôn ngữ C/C++ nói riêng.

Sau đây là phần lý thuyết, các bạn có thể xem bất cứ khi nào tại link dưới đây:

https://cpp.daynhauhoc.com

Ngoài ra còn có series các videos hướng dẫn do chính founder của DAYNHAUHOC làm ra với mục đích làm cho khóa học thêm sinh động và các bạn dễ tiếp cận hơn.

Có thể tham khảo khóa học này tại đây:

https://www.udemy.com/c-co-ban-danh-cho-nguoi-moi-hoc-lap-trinh/

Đăng ký mua với giá ưu đãi nhất? Click vào link dưới đây:

https://docs.google.com/forms/d/e/1FAIpQLScHY3aMUaG81hafWHL8Gzhj_ZUskRVsyOJS0P_Xr7gPoe29FA/viewform

 

Mọi chi tiết vui lòng xem thêm tại DAYNHAUHOC.COM

Tìm kiếm nhị phân (ví dụ trên c++)

Ý tưởng tương tự thuật toán sắp xếp quá nổi tiếng QuickSort.

Sau mỗi bước tìm kiếm thì số phần tử trong lần xét sau chỉ còn 1 nửa. Cho nên thời gian thực thi của thuật tìm kiếm này là O(LogN).

sample:

 

<br />// mảng a chứa các phần tử đã được sắp xếp (điều kiện cần cho thuật toán này).

// n là số lượng phần tử trong mảng a này.

// x là phần tử cần tìm
int TimKiemNhiPhan(int a[MAX], int left, int right, int mid, int x)
{
if (left > right)return -1;
if (a[mid] == x)return mid;
if (a[mid] > x)return TimKiemNhiPhan(a, left, mid-1, (left+(mid-1))/2, x);
return TimKiemNhiPhan(a, mid + 1, right, (mid + 1 + right) / 2, x);
}

void Result()
{
int res = TimKiemNhiPhan(a, 0, n - 1, (n - 1) / 2, x);
if (vt == -1)
cout << "\nKhong tim thay"<<" "<< x;
else cout << "\nTim thay:"<<" "<<x << " "<<"tai vi tri la:" << vt;
}

Bài toán Mã đi tuần (ví dụ trên c++)

#include <iostream>
#include <iomanip>

using namespace std;

// Input
int n = 8;
int x, y;

// Output
int BanCo[8][8];

int dx[] = {-2, -1, +1, +2, +2, +1, -1, -2};
int dy[] = {+1, +2, +2, +1, -1, -2, -2, -1};

void Xuat()
{
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
cout << setw(3);
cout << BanCo[i][j] << " ";
}
cout << endl;
}
cout << endl;
}

// Tim 1 trong 8 o xung quanh cua (x,y) de dat Ma
void MaDiTuan(int x, int y, int buoc)
{
if (buoc > n*n)
Xuat();
else
{
// Xet 8 o xung quanh
for (int k=0; k<8; k++)
{
int xx = x + dx[k];
int yy = y + dy[k];

// Nằm trong bang nxn11111111111111111111
if (xx>=0 && yy>=0 && xx<n && yy<n)
if (BanCo[xx][yy]==0) // Chua có Mã
{
BanCo[xx][yy] = buoc;
//Xuat();
MaDiTuan(xx, yy, buoc+1);
BanCo[xx][yy]=0;
}
}
}
}

int main()
{
// Nhap x, y
x = 7;
y = 3;
n=8;

for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
BanCo[i][j]=0;
}
}

int buoc=1;
BanCo[x][y] = buoc;
MaDiTuan(x, y, buoc+1);

return 0;
}

Tìm dãy con tăng dài nhất (Ví dụ đơn giản trên C++)

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

// Input
#define MAX 1010

int a[MAX]={7, 9, 15, 3, 9, 10, 7, 5};
int n=8;

// Output
int f[MAX];
int pre[MAX];

void TinhF()
{
// Khởi tạo
for (int i=0; i<n; i++)
pre[i]=-1;

f[0]=1;
for (int i=1; i<n; i++)
{
f[i]=1;
for (int j=0; j<i; j++){
if (a[j] <= a[i]){
if (f[i] < f[j]+1)
{
f[i] = f[j]+1;
pre[i] = j;
}
}
}
}
}
vector<int> daycontang;
void TruyVet()
{
int gtmax=f[0];
int vitri = 0;

for (int i=1; i<n; i++)
if (gtmax < f[i])
{
gtmax = f[i];
vitri=i;
}

// Tim day con tang dai nhat
for (int i=vitri; i!=-1; i=pre[i])
daycontang.push_back(a[i]);
int len = daycontang.size();
for (int i=len-1; i>=0; i--)
cout << daycontang[i] << " ";
cout << endl << "Do dai: " << gtmax;
}

int main()
{
TinhF();
TruyVet();
return 0;
}

[URI ONLINE JUDGE] – 1328 – Go Easy

The mayor of a city wants to introduce a new transport system to simplify the life of its inhabitants. That will be done via the use of a debit card, which the mayor named “GoEasy”. There are two means of transportation in the city: trains and buses. The train system is “zone based” whereas the bus system is “journey based”. The fare for a journey is computed as follows:

  • There is an initial two money units fare for entering the transport system, regardless of the initial means of transportation.
  • When travelling by train a customer pays four money units for each change of zone.
  • When travelling by bus a customer pays one money unit each time she/he boards a bus.

A transport system map will provide information about the stations belonging to each zone, and the sequence of stations for each bus and train itinerary. Buses and trains move in both directions in each itinerary, and no train or bus goes through the same station twice during a single trip through an itinerary. It is always possible to go from any station to any other station using trains and/or buses. The rules for computing fares are strict: if during a train journey a customer enters a given zone twice, she/he is charged twice; similarly, if during a bus journey a customer boards twice the bus for the same itinerary, she/he is charged twice.

In the transport map above a customer can travel from station 2 to station 4 paying just two money units, by using line T1, since they are in the same zone. But if the customer needs to go from station 2 to 5, then the best is to take the bus B3 to station 10 and then take the bus B2 to station 5, paying in total four money units. Rather than tracking the whole trip of each passenger, the idea of the mayor is that machines will be placed in all stations, and travellers are supposed to swipe their personal GoEasy travel card only when starting AND finishing the whole journey. Since all the machines are interconnected into a network, based on the departure and arrival stations the system can compute the minimum cost possible for the trip, and that amount is charged from the traveller’s debit card. All that is missing is a computer system for doing the calculations for the fare to be deducted. So, given the map of the transport system in the city, you must write a program to compute the minimum fare the customer should pay to travel between two given stops/stations.

Input

The input contains several test cases. The first line of a test case contains two integers Z and S, which indicate respectively the number of zones (1 ≤ Z ≤ 30) and the number of train/bus stations in the city (1 ≤S ≤ 100). Each station has a unique identification number ranging from 1 to S, and each station belongs to exactly one zone. Each of the following Z lines describes the stations belonging to a zone. The description for a zone starts with an integer K indicating the number of stations (1 ≤ KS) in the zone, followed by Kintegers representing the stations in the zone. After that comes a line with two integer numbers T and B, representing respectively the number of train itineraries (1 ≤ T ≤ 50) and the number of bus itineraries (1 ≤B ≤ 50). Next comes T lines describing train itineraries, followed by B lines describing bus itineraries. The description of each itinerary consists of a line containing an integer L indicating the number of stations (2 ≤ LS) in the itinerary, followed by L integers specifying the sequence of stations in the itinerary. Finally it comes a line with two integers X and Y (1 ≤ XS, 1 ≤ YS and XY ), specifying that the customer travelled from station X to station Y . The end of input is indicated by Z = S = 0.

Output

For each test case your program should output one line, containing an integer representing the amount to be deducted from the traveller’s GoEasy card.

Sample Input Sample Output
3 15
2 8 9
7 2 3 4 7 12 13 14
6 1 5 6 10 11 15
3 3
5 1 2 3 4 5
3 1 6 11
4 4 8 12 11
6 2 7 12 13 14 15
3 5 10 15
6 1 2 3 8 9 10
11 6
3 15
2 8 9
7 2 3 4 7 12 13 14
6 1 5 6 10 11 15
3 3
5 1 2 3 4 5
3 1 6 11
4 4 8 12 11
6 2 7 12 13 14 15
3 5 10 15
6 1 2 3 8 9 10
11 5
0 0
2
4

 

my solution:

<br />// by David H Ng & Karry Smith
#include
#include
#include
#include
#include
#include
<map> #include </map>

using namespace std;

struct Station {
int zone;
vector<pair<int, int> > transports;

Station() : zone(-1),
transports(vector<pair<int, int> >()) { }
};

struct Transport {
char type;
vector itineraries;
};

struct Edge {
pair<int, int> to;
int cost;

Edge(pair<int, int> t, int c) : to(t), cost(c) { }
};

struct Node {
int distance, station, transport;
vector edges;
bool edgesCalculated;
pair<int, int> previous;

Node() : station(-1), transport(-1), distance(INT_MAX),
edges(vector()), edgesCalculated(false),
previous(pair<int, int>(-1, -1)) { }
Node(int st, int tr) : station(st), transport(tr),
distance(INT_MAX), edges(vector()), edgesCalculated(false),
previous(pair<int, int>(-1, -1)) { }
};

vector stations;
vector transports;
vector<vector > nodes;

struct NodeReference {
pair<int, int> pos;
int distance;

NodeReference(pair<int, int> p) : pos(p)
{
distance = nodes[pos.first][pos.second].distance;
}

bool operator<(const NodeReference other) const { return distance > other.distance;
}
};

void initNodes(int from, int to) {
nodes = vector<vector >(stations.size() + 2);

vector internal;
internal.push_back(Node(from, -1));
internal[0].distance = 2;
nodes[stations.size()] = internal;

internal[0] = Node(to, -1);
nodes[stations.size() + 1] = internal;

for(int i = 0; i < stations.size(); ++i) {
const Station& s = stations[i];

for(int j = 0; j < s.transports.size(); ++j) {
Node n(i, j);

if (i == from)
nodes[stations.size()][0].edges.push_back(Edge(pair<int, int>(i, j),
transports[s.transports[j].first].type == 'B' ? 1 : 0));
if (i == to)
n.edges.push_back(Edge(pair<int, int>(stations.size() + 1, 0), 0));

if (j >= nodes[i].size())
nodes[i].resize(j + 1);
nodes[i][j] = n;
}
}
}

int getMinPrice(int from, int to) {
initNodes(from, to);

vector heap;
vector<vector > visited(nodes.size());
for(int i = 0; i < nodes.size(); ++i) {
visited[i] = vector(nodes[i].size(), false);
}

heap.push_back(NodeReference(pair<int, int>(stations.size(), 0)));

while(!heap.empty()) {
pair<int, int> current = heap.front().pos;
Node& minNode = nodes[current.first][current.second];
pop_heap(heap.begin(), heap.end());
heap.pop_back();

if (visited[current.first][current.second])
continue;

if (current.first == stations.size() + 1)
break;

if (minNode.distance == INT_MAX)
break;

if (!minNode.edgesCalculated && current.first < stations.size()) {
static const int Offsets[] = { 1, -1 };

const Station& st = stations[minNode.station];
const pair<int, int>& p = st.transports[minNode.transport];
const Transport& t = transports[p.first];
int index = p.second;

// Nodes in station

int cost;
for(int i = 0; i < st.transports.size(); ++i) {
if (st.transports[i] == p)
continue;
cost = 0;
int nextIndex = st.transports[i].first;
const Transport& nextT = transports[nextIndex];
if (nextT.type == 'B')
cost = nextIndex == p.first ? 0 : 1;

minNode.edges.push_back(Edge(pair<int, int>(minNode.station, i), cost));
}

// Next stations using this transport
for(int j = 0; j < 2; ++j) {
if(index + Offsets[j] < 0 || index + Offsets[j] >= t.itineraries.size())
continue;

int nextStationIndex = t.itineraries[index + Offsets[j]];
const Station& nextStation = stations[nextStationIndex];

for(int k = 0; k < nextStation.transports.size(); ++k) {
int nextTransportIndex = nextStation.transports[k].first;
if (nextTransportIndex != p.first)
continue;
const Transport& nextTransport = transports[nextTransportIndex];

int cost = 0;
if(nextTransport.type == 'T')
cost = st.zone != nextStation.zone ? 4 : 0;

minNode.edges.push_back(Edge(pair<int, int>(nextStationIndex,
k), cost));
}
}

minNode.edgesCalculated = true;
}

for(int i = 0; i < minNode.edges.size(); ++i) {
int alt = minNode.distance + minNode.edges[i].cost;
Node& neighbour = nodes[minNode.edges[i].to.first][minNode.edges[i].to.second];

if (!visited[minNode.edges[i].to.first][minNode.edges[i].to.second] &&
alt < neighbour.distance) { neighbour.distance = alt; neighbour.previous = current; heap.push_back(NodeReference(minNode.edges[i].to)); push_heap(heap.begin(), heap.end()); } } visited[current.first][current.second] = true; } return nodes[stations.size() + 1][0].distance; } Transport readTransport() { int k; cin >> k;
vector itineraries(k);

for(int i = 0; i < k; ++i) { cin >> itineraries[i];
--itineraries[i];
}

Transport result;
result.itineraries = itineraries;

return result;
}

int main() {
int zoneCount, stationCount;

while(cin >> zoneCount >> stationCount &&
zoneCount > 0 && stationCount > 0) {
stations = vector(stationCount);

for(int i = 0; i < zoneCount; ++i) { int k; cin >> k;

for(int j = 0; j < k; ++j) { int value; cin >> value;
stations[value - 1].zone = i;
}
}

int trainCount, busCount;
cin >> trainCount >> busCount;

transports = vector(trainCount + busCount);
for(int i = 0; i < transports.size(); ++i) {
transports[i] = readTransport();
transports[i].type = i < trainCount ? 'T' : 'B';

for(int j = 0; j < transports[i].itineraries.size(); ++j) {
stations[transports[i].itineraries[j]]
.transports.push_back(pair<int, int>(i, j));
}
}

int from, to;
cin >> from >> to;

int result = getMinPrice(from - 1, to - 1);

cout << result << '\n';
}
}

8 puzzle (Bài toán Ta canh)


#include <iostream>
using namespace std;
#define MAX 3

// the result state must be
int Final_State[MAX][MAX] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 0}
};

// initialize
int Current_State[MAX][MAX] = {
{0, 1, 3},
{4, 2, 5},
{7, 8, 6}
};

// moving step (0,-1) that means (i, j-1) => Move left
// moving step (-1,0) that means (i-1, j) => Move up
// moving step (0,+1) that means (i, j+1) => Move right
// moving step (+1,0) that means (i+1, j) => Move down
int di[4] = {0, -1, 0, +1};
int dj[4] = {-1, 0, +1, 0};

int DD[13][MAX][MAX];
int nDD = 0;
int step = 0;

void Swapper(int &a, int &b){ a = a^b; b = a^b; a = a^b; }

// find the index of an element in matrix
int FindIndex(int a[MAX][MAX], int row, int column, int &rowIndex, int &columnIndex, int x){
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(a[i][j] == x){
rowIndex = i;
columnIndex = j;
return 1;
}
}
}
return -1;
}

int TotalMoving(int T[MAX][MAX]){
int total = 0;
int rowIndex, columnIndex;
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(T[i][j] != 0){
FindIndex(Final_State, MAX, MAX, rowIndex, columnIndex, T[i][j]);
total += (abs(rowIndex-i) + abs(columnIndex-j));
}
}
}
return total;
}
// copy all element from A to B
void ArrayCopy(int a[MAX][MAX], int b[MAX][MAX], int na, int nb){
for(int i=0; i<na; i++){
for(int j=0; j<nb; j++){
b[i][j] = a[i][j];
}
}
}

void PrintArray(int a[MAX][MAX], int row, int column){
for(int i=0; i<row; i++){
for(int j=0; j<column; j++){
cout << a[i][j] << " ";
}
cout << endl;
}
}

bool IsDuplicate(int T1[MAX][MAX], int T2[MAX][MAX]){
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(T1[i][j] != T2[i][j]){
return false;
}
}
}
return true;
}

// T: current state
bool IsVisited(int T[MAX][MAX]){
for(int i=0; i<nDD; i++){
if(IsDuplicate(T, DD[i])){
return true;
}
}
return false;
}

int Solve(){
int i_zero_index, j_zero_index;

int minSum;
int T[MAX][MAX];
int temp[MAX][MAX];

while(1){
cout <<"\nstep " << step + 1 << ":" << endl;
PrintArray(Current_State, MAX, MAX);
// param 0: find index of zero
FindIndex(Current_State, MAX, MAX, i_zero_index, j_zero_index, 0);

minSum = 100;
for(int i=0; i<4; i++){
int i_neighbour_index = i_zero_index + di[i];
int j_neighbour_index = j_zero_index + dj[i];
if(i_neighbour_index >= 0 && i_neighbour_index < MAX && j_neighbour_index >= 0 && j_neighbour_index < MAX){
ArrayCopy(Current_State, temp, MAX, MAX);
Swapper(temp[i_zero_index][j_zero_index], temp[i_neighbour_index][j_neighbour_index]);
int sum = TotalMoving(temp);
if(sum < minSum && IsVisited(temp) == false){
minSum = sum;
ArrayCopy(temp, T, MAX, MAX);
}
}
}
ArrayCopy(T, Current_State, MAX, MAX);
ArrayCopy(Current_State, DD[nDD++], MAX, MAX);
step++;
if(minSum == 0){
return 1;
}
if(step == 13){
return 0;
}
}
return 0;
}

int main()
{
ArrayCopy(Current_State, DD[nDD++], MAX, MAX);
if(Solve() == 0){
cout << "Failed !";
}
else{
cout << "\nStep " << step + 1 << ":" << endl;
PrintArray(Current_State, MAX, MAX);
cout << "\nSuccess!" << endl;
}
return 0;
}

TSP (Travelling Salesman problem)


#include <iostream>
using namespace std;
#define MAX 100
#define INF 354754546

int n = 5;
int step = 0;
int path[MAX];
int visited[MAX];
int array[MAX][MAX] = {
{INF, 3, 4, 2, 7},
{3, INF, 4, 6, 3},
{4, 4, INF, 5, 8},
{2, 6, 5, INF, 6},
{7, 3, 8, 6, INF}
};

void TSP(int start)
{
int min = 0;
while(step < n)
{
for(int i=0; i<step; i++) // find minimum cost.
{
if(visited[i] == 0 && array[start][i] < array[start][min])
{
min = i;
}
}
array[start][min] = array[min][start] = INF;
start = min; // set the next start point.
path[step++] = start; // next step.
visited[start] = 1; // set this point visited.
}
}

void PrintPath()
{
for(int i=0; i<n; i++){
cout << path[i] << " ";
}
}
int main()
{
TSP(0); // start from the first point
PrintPath();
return 0;
}