thảo luận [Học Tập] Topic thuật toán

Aristides · 10/10/21

WoodyTheEvil đã nói:
có tips hay tài liệu nào để tham khảo chuyển đổi đệ quy sang loop ko bác :stick:
nhiều bài e vẫn chưa mường tượng ra cách đổi như thế nào nữa

Không

chuyển đổi đệ quy sang loop thì nó là chuyển sang quy hoạch động rồi

Ngày Được Tự Do · 10/10/21

WoodyTheEvil đã nói:
có tips hay tài liệu nào để tham khảo chuyển đổi đệ quy sang loop ko bác :stick:
nhiều bài e vẫn chưa mường tượng ra cách đổi như thế nào nữa

đệ quy sang loop độ phức tạp tương đương thì dùng stack, queue. Còn cách sang quy hoạch động là khó nghĩ hơn và đương nhiên là nhanh hơn, tốn ít bộ nhớ hơn

realhaidinh · 10/10/21

WoodyTheEvil đã nói:
có tips hay tài liệu nào để tham khảo chuyển đổi đệ quy sang loop ko bác :stick:
nhiều bài e vẫn chưa mường tượng ra cách đổi như thế nào nữa

Bác tìm ra dc quy luật thì sẽ khử đệ quy dc
https://thanhcuong.wordpress.com/2010/12/13/dệ-quy-quy-chế-v-cch-khử/

Ngày Được Tự Do · 10/10/21

greezn đã nói:
Em mới nhập môn khoa học máy tính ạ, có bài tập sau em phải trình bày ra slide, về cơ bản em biết cách giải nhưng trình bày thuật toán ra thì em chưa biết thế nào, các bác giúp em với em cảm ơn
Xem tệp đính kèm 808107

sao mỗi 2 lần là được mà, từ hộp 11 chuyển 2 sang hộp 6, lần 2 chuyển 1 sang hộp 7. 2 lần là có 3 hộp 8 rồi

WoodyTheEvil · 10/10/21

realhaidinh đã nói:
Bác tìm ra dc quy luật thì sẽ khử đệ quy dc
https://thanhcuong.wordpress.com/2010/12/13/dệ-quy-quy-chế-v-cch-khử/

Tks bác,

để e tham khảo.
Hiện tại tất cả các bài QHĐ đã làm đều bằng đệ quy + memoize với hash table. Nhưng có vẻ vẫn chưa tối ưu lắm bù lại dễ suy nghĩ hơn

davinci1207 · 10/10/21

WoodyTheEvil đã nói:
Tks bác, để e tham khảo.
Hiện tại tất cả các bài QHĐ đã làm đều bằng đệ quy + memoize với hash table. Nhưng có vẻ vẫn chưa tối ưu lắm bù lại dễ suy nghĩ hơn

Phải luyện tập để thay đổi tư duy, thay vì nghĩ theo hướng top-down thì nghĩ theo hướng bottom-up. Bottom-up DP không phải là recursive -> iterative.

greezn · 10/10/21

Ngày Được Tự Do đã nói:
sao mỗi 2 lần là được mà, từ hộp 11 chuyển 2 sang hộp 6, lần 2 chuyển 1 sang hộp 7. 2 lần là có 3 hộp 8 rồi

bác đọc kỹ bác ơi :v số đồ vật chuyển bằng số đồ vật có sẵn mà bác :v

Ngày Được Tự Do · 10/10/21

greezn đã nói:
bác đọc kỹ bác ơi :v số đồ vật chuyển bằng số đồ vật có sẵn mà bác :v

Giải luôn đi fen, đề bài thuật toán là phải giải mẫu 1 bài cho người ta hiểu đề, rồi cho các bộ input

Thạch Sanh_4.0 · 11/10/21

tranchan đã nói:
làm thế nào luyện mấy bài thuật toán khó thế nhỉ

nhớ cách làm của 1 bài toán cụ thể, nhớ càng nhiều bài toán thì càng tốt, sau này có thể tự tư duy sang các bài toán kiểu tương tự.

Ngày Được Tự Do · 11/10/21

ae thử bài này, đề bài đơn giản: "có bao nhiêu ước của N giai thừa mà chia hết cho D"

nashwade · 11/10/21

Ngày Được Tự Do đã nói:
ae thử bài này, đề bài đơn giản: "có bao nhiêu ước của N giai thừa mà chia hết cho D"

Phân tích N!, D thành tích thừa số nguyên tố. Lấy hiệu 2 mảng số mũ, nếu có số âm thì kết quả là 0. Không thì kết quả = tích(số mũ + 1).

Ngày Được Tự Do · 11/10/21

nashwade đã nói:
Phân tích N!, D thành tích thừa số nguyên tố. Lấy hiệu 2 mảng số mũ, nếu có số âm thì kết quả là 0. Không thì kết quả = tích(số mũ + 1).

hay quá fen, thế bài này chỉ cần thuật toán phân tích nguyên tố là được, cứ tưởng khó lắm nữa

Yêu em Thu Nga CN12 ptit · 11/10/21

Ngày Được Tự Do đã nói:
hay quá fen, thế bài này chỉ cần thuật toán phân tích nguyên tố là được, cứ tưởng khó lắm nữa

thím ý trình cao lắm bác, khéo đang làm cho google ấy

dunglucbac · 11/10/21

có bài này cũng muốn góp vui với các bác

Screen Shot 2021-10-11 at 8.56.51 PM.png

thuyduong2007 · 11/10/21

dunglucbac đã nói:
có bài này cũng muốn góp vui với các bác Xem tệp đính kèm 810779

bài này làm quy hoạch động là xong mà.

Mã:

distant[i][j] = path[i][j] + min(distant[i+1][j], distant[i][j+1])

Thêm điều kiện xử lý mấy trường hợp biên nữa là xong.

turky mark · 11/10/21

anh nào có kênh hoặc video giải thuật toán mà giải thích kĩ như này ko nhỉ:

gnut102 · 11/10/21

Các anh giúp e làm bài này bằng C với mà không dùng tới mảng ạ, e lên gg tìm ng ta toàn hướng dẫn dùng mảng để giải ạ

(. Nếu làm bằng if else thì càng tốt, em cảm ơn

tien_manh_a2 · 12/10/21

Mình đoán là bạn chưa search đúng keyword hoặc có thể đọc lời giải không hiểu nên mình code hộ bạn vậy
:big_smile:

JavaScript:

function median(a, b, c, d, e) {
  if (a >= b) { /* 1st comparision */
    a = a + b; b = a - b; a = a - b; // swap
  }
  if (c >= d) { /* 2nd comparision */
    c = c + d; d = c - d; c = c - d;
  }
  // now we have: a < b, c < d
  if (b >= d) { /* 3rd comparision */
    a = a + c; c = a - c; a = a - c;
    b = b + d; d = b - d; b = b - d;
  }
  // now d > (a and b and c) => d is not median
  if (c >= e) { /* 4th comparision */
    c = c + e; e = c - e; c = c - e;
  }
  // now we have: a < b, c < e
  if (b > e) { /* 5th comparision */
    if (a > e) return a; else return e; /* 6th comparision */
  } else { // => e is not median
    if (b > c) return b; else return c; /* 6th comparision */
  }
}

Còn đây là link lời giải https://cs.stackexchange.com/a/45379.

dunglucbac · 12/10/21

thuyduong2007 đã nói:
bài này làm quy hoạch động là xong mà.

Mã:

distant[i][j] = path[i][j] + min(distant[i+1][j], distant[i][j+1])

Thêm điều kiện xử lý mấy trường hợp biên nữa là xong.

mình nghĩ đây là bài toán tìm đường đi ngắn nhất code của mình thì như này

Mã:

while q:
        curr = q.popleft()
        i = curr.x
        j = curr.y

        n = matrix[i][j]
        if n == 'end':
            return

        row = [0, 1]
        col = [1, 0]
        for k in range(len(row)):
            x = i + row[k]
            y = j + col[k]

            if (0 <= x < N) and (0 <= y < N):
                next = Cell(x, y, curr)
                key = (next.x, next.y)

                if key not in visited:
                    q.append(next)
                    visited.add(key)

Yêu em Thu Nga CN12 ptit · 12/10/21

dunglucbac đã nói:

mình nghĩ đây là bài toán tìm đường đi ngắn nhất code của mình thì như này

Mã:

while q:
        curr = q.popleft()
        i = curr.x
        j = curr.y

        n = matrix[i][j]
        if n == 'end':
            path = []
            getPath(curr, path)
            return path

        row = [0, 1]
        col = [1, 0]
        for k in range(len(row)):
            x = i + row[k]
            y = j + col[k]

            if isValid(x, y, N):
                next = Node(x, y, curr)
                key = (next.x, next.y)

                if key not in visited:
                    q.append(next)
                    visited.add(key)

Này qhđ căn bản làm được mà, y hệt bài trên web trường e, mà thêm cho đi chéo nữa.
Cho bảng A[] kích thước N x M (N hàng, M cột). Bạn được phép đi xuống dưới, đi sang phải và đi xuống ô chéo dưới. Khi đi qua ô (i, j), điểm nhận được bằng A[j].

Hãy tìm đường đi từ ô (1, 1) tới ô (N, M) sao cho tổng điểm là nhỏ nhất.

C++:

#include<bits/stdc++.h> #define faster() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); using namespace std; typedef double ld; typedef long long ll; typedef unsigned long long ull; void solve(int a[500][500],int n, int m){ vector<vector<int> >dp(n+1,vector<int>(m+1,INT_MAX)); dp[0][0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+a[i-1][j-1]; } } cout<<dp[n][m]; } int main(){ faster(); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; int a[500][500]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++) cin>>a[i][j]; } solve(a,n,m); cout<<'\n'; } return 0; }

thảo luận [Học Tập] Topic thuật toán

Senior Member

Senior Member

Senior Member

Senior Member

Member

Đã tốn tiền

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Member

Member

Senior Member

Senior Member

Junior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này