Mọi người có thể chỉ em thuật toán bài này đc không ạ?
Viết bằng ngôn ngữ gì?
có trường hợp Linh khùng cứ đổi qua trái rồi lại quay về phải rồi lại qua trái liên tục không nhi?
Con bé này phiền ghê, sinh nhật thì tổ chức tiệc đứng đi, mà sinh nhật thì phải quẩy mạnh chứ sao lại không muốn to tiếng ta.
viết bằng nn gì liên quan gì tới thuật toán :V
đầu tiên là xét vị trí hiện tại: với k lần đổi chỗ có thể trở về vị trí hiện tại được ko. Sau đó dịch chuyển 1 vị trí, tiếp tục hỏi với k-1 lần đổi chỗ có thể trở về vị trí này được ko, v.v… tiếp tục sẽ mò ra lời giải :V
-Nếu Linh muốn nói chuyện 1 cách hiệu quả thì Linh sẽ đổi chỗ với tất cả mọi người lần lượt.
-Giả sử Linh ngồi ghế thứ 1 thì Linh sẽ lần lượt đổi chỗ phía bên phải cho tới ghế thứ n (1->n) rồi sau đó lần lượt đổi về vị trí ban đầu(n->1).
-Vậy cứ 1 lần đổi từ vị trí đầu về cuối Linh sẽ mất n-1 lần đổi chỗ.
-Dùng chia lấy dư ta sẽ biết được số chỗ ngồi mà cô ấy đã ngồi cuối cùng trong bữa tiệc
Về vị trí hiện tại làm gì? Vì đổi chỗ không theo quy luật (k biết qua phải hay qua trái) thì làm sao biết đc lần đổi k em ý ngồi đâu. Linh xinh nhưng bị khùng
Bàn tròn hay bàn dài 
Xung quanh bàn lớn nên chắc là bàn tròn.
Cách giải bài toán này đầu tiên phải đi từ trường hợp nhỏ nhất. Nếu n vô hạn, k = 1, thì có 2 phép chọn ở index = -1 || 1. K = 2 thì có 3 cách chọn ở index = -2 || 0 || 2. K = 3 thì có 4 cách chọn ở index = -3 || -1 || 1 || 3. Vậy có thể nhận ra công thức với N là vô cùng và bàn là bàn tròn thì số cách chọn sẽ bằng K + 1. Đấy là khi N vô hạn và bàn tròn. Vậy với K <= N / 2 thì có kết quả là K + 1. Vậy với K > N / 2 thì sao? Biện luận thêm chắc là sẽ ra công thức.
hỏi số các số ghế có thể là ghế cuối cùng mà. Vậy câu hỏi đầu tiên đặt ra là ghế hiện tại của Linh có thể là ghế cuối cùng hay ko? Nếu k chẵn thì câu trả lời là có, nếu k lẻ thì chỉ quay về ghế hiện tại được nếu k chia hết cho n (đổi chỗ k/n vòng liên tục bên trái hoặc liên tục bên phải).
tính được ghế hiện tại có thể là ghế cuối cùng hay ko rồi thì 2 ghế kế bên trái phải cũng tương tự: đổi chỗ 1 lần qua trái hoặc phải, vậy còn k-1 lần đổi chỗ. Tiếp tục đặt câu hỏi tương tự là xong.
bàn tròn thì chia ra 2 th n lẻ và n chẵn. Nếu n chẵn thì n ghế sẽ chia thành 2 loại ghế trắng/đen. Nếu n lẻ thì ghế cùng màu hoặc tùy thuộc vào k có >= n/2 hay >= n hay ko :V Mất thời gian :V
ví dụ n chẵn:
- với k >= n, sẽ có đúng n/2 số ghế có thể là ghế cuối cùng.
Chứng minh: đánh số ghế từ 1 tới n. Vì n chẵn nên chia thành 2 loại ghế: ghế có số chẵn và ghế có số lẻ. Nếu k lẻ thì chỉ có ghế loại số chẵn mới có thể là ghế cuối cùng: bắt đầu từ 1, vì k lẻ nên ko thể quay về ghế hiện tại (số 1) để nó là ghế cuối cùng. k cũng ko thể chia hết cho n vì n chẵn, k lẻ. Vậy nếu k lẻ thì chỉ có số ghế số chẵn mới có thể là ghế cuối cùng. Và vì k >= n nên Linh đổi chỗ được nhiều hơn 1 vòng, đi qua hết các ghế chẵn, vậy ở đây n/2 (ghế số chẵn) là đáp án. Nếu k chẵn thì chứng minh tương tự, chỉ khác ở chỗ chỉ có các ghế số lẻ mới có thể là ghế cuối cùng, đáp án vẫn là n/2 (ghế số lẻ) - với n > k >= n/2, cũng có đúng n/2 ghế có thể là ghế cuối cùng.
Chứng minh: tương tự, nhưng vì k < n nên Linh ko thể đi qua hết n ghế nếu chỉ dịch chuyển qua bên phải. Nhưng vì Linh còn dịch chuyển qua trái được nên vì k >= n/2 Linh dịch chuyển được nửa vòng bên trái hoặc nửa vòng bên phải, cũng đi tới được n ghế, vậy đáp án tương tự k >= n, là n/2 ghế. - với k < n/2 :V :V Nếu Linh chỉ dịch qua phải thì Linh sẽ đi tới được k+1 ghế [1, 2, 3, …, k+1]. Nếu Linh chỉ dịch qua trái thì đi tới được k+1 ghế bên trái [1, n, n-1, …, n-k+1]. Giao 2 tập hợp lại, Linh đi được tới 2k+1 ghế, trong 2k ghế đó, nếu k chẵn thì có k+1 ghế lẻ và k ghế chẵn (ví dụ k=2 thì ghế chẵn là n và 2, ghế lẻ là 1, 3 và n-1), nếu k lẻ thì có k ghế lẻ và k+1 ghế chẵn. Lập luận tương tự, khi k chẵn thì đáp án là số ghế lẻ = k+1. Khi k lẻ thì đáp án là số ghế chẵn, cũng bằng k+1.
Vậy với n chẵn, đáp án là n/2 nếu k >= n/2 hoặc k+1 nếu k < n/2
n lẻ nhiều th hơn, quá dễ xin để bạn đọc tự trả lời :V :V :V
à, hiểu rùi, tại tui cứ loay hoay “đi tìm cái ghế cuối cùng”.
thanks
mò từ từ cũng ra nè :V Mà nó là giao 2 tập hợp bên trái và bên phải, nên với k = n/2 (n chia hết cho 2 thì n chẵn) thì kq chỉ có k ghế thôi, ví dụ 0 1 2 3 thì ghế số 2 và ghế số -2 là một, nên chỉ có 2 cách chọn :V
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?