Dùng sigle linklist đi, được đó.
mình đang có một bài tập cuối kỳ trong đó có một phần mình làm vẫn không được tốt lắm mong các bạn chỉ giúp nhé :
tạo một mảng (n phần tử biết trước) chuỗi ngẫu nhiên 6 ký tự không trùng lắp với các chuỗi trước đó
ý tưởng củ mình là
Visual C# Code:
//tạo mới một mảng các ký tự sẽ được chứa trong chuỗi char[] MangKyTu = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','V','W','Y','Z','0','1','2','3','4','5','6','7','8','9'}; //tạo một chuỗi ngẫu nhiên { chuoi = chuoi + MangKyTu[t]; }
sau đó tiến hành dò tìm xem chuỗi tìm được có trùng với các phần tử trước đó không, nếu trùng thì tiến hành tạo ngẫu nhiên lại, nếu không trùng thì cập nhật vô mảng
các này của minh thử với số phần tử cần tìm nhỏ thì được, lên đến cỡ 100.000 thì chậm kinh khủng
ai có các nào hay chỉ giúp mình với
cần gấp lắm
Dùng sigle linklist đi, được đó.
Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.
Đề bài của bạn ý như thế này phải không?
Mình chỉ gợi ý được vậy thui, sắp phải làm bài tập lớn rùi. Có gì không hiểu trao đổi sau.1. Ví dụ các chuối sau:
abcdef
aaffes
mmsas
.......
2. Đó là các chuỗi gồm 6 ký tự không trùng lặp nhau ?
3. Vậy mình coi mỗi chuỗi đó là một Node của linklist
4. Tiến hành các thao tác sử lý so sánh và các thao tác với linklist
Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.
nhc chỉ có một lời khuyên là sử dụng StringBuilder thay cho String. Điều này sẽ cải thiện đáng kể performance.
Keep moving forward!
... Retired ...
Hãy suy nghĩ thuật toán mới đi, cách làm hiện nay của bạn sẽ cực kỳ tốn kém vì độ phức tạp lên tới O(n*n).
Một cách làm với độ phức tạp O(n) là:
Thay vì phát sinh ra n chuổi 6 ký tự ngẫu nhiên, hãy phát sinh ra n số nguyên ngẫu nhiên, rồi ánh xạ mỗi số nguyên đó ra thành một chuổi 6 ký tự(ánh xạ này phải là ánh xạ một-một). Để n số nguyên phát sinh ra không được trùng nhau, ta có thể làm như sau:
+ gọi N1 là số nguyên ngẫu nhiên đầu tiên
+ N2 = N1 + một số ngẫu nhiên nhỏ nào đó
+ ...
+ Nn = N(n-1) + một số ngẫu nhiên nhỏ nào đó
Sau khi xây dựng được ánh xạ một - một đó bạn sẽ thấy được khoảng giá trị của các số nguyên cần phát sinh ngẫu nhiên.
Ai có cách làm khác thì bàn cho vui nha...
Đã được chỉnh sửa lần cuối bởi pmtuan : 11-03-2008 lúc 09:38 PM.
Viết một bản nháp đơn giản
Visual C# Code:
class RandomGenerator { private Random _rdmizer; /* * PROPERTIES */ { } { } /* * CONSTRUCTOR */ { _store[cnt] = ""; _capacity = DEFAULT_CAPACITY; } /* * METHODS */ // Just only use to generate a random string { { builder.Append(_GenerateChar()); } } // Add a string to store { _store[_current++] = _in_str; } // Generate the next string to the store { Next(); Add(_str); return _str; } // check whether a string stored already { { } } // get all stored strings { return _store; } // generate a random character { int _num; { _num = _rdmizer.Next(48,122); return chr; } }
Rồi test thử:
Visual C# Code:
class Program { { Console.WriteLine("Start: " + start); generator.Next(); Console.WriteLine("Store: " + store[cnt]); } }
Kết quả:
Bài tớ viết có chú thích rồi, các bạn đọc là hiểu. Đây là phương pháp trâu đầm, cứ thế mà cày codeCode:Start: deXVjh Store: N2je8S Store: qlfGf3 Store: V88JZH Store: IfjVcG Store: rH6nVB Store: qiKXqP Store: KCl7TJ Store: wQ1Co0 Store: OfsVxW Store: POCvSk Press any key to continue . . .
+ Tạo một store chứa danh sách các chuỗi
+ Tạo hàm chế random chuỗi
+ Kiểm tra chuỗi đó có tồn tại trong danh sách chưa?
+ Chưa có thì thêm vào, ngược lại thì lại chế random chuỗi tiếp.
Đã được chỉnh sửa lần cuối bởi Xcross87 : 11-03-2008 lúc 11:00 PM.
None!
Không biết Pete có chạy thử với 1 triệu chưa ? Đo thởi gian chạy xem thế nào ?
Keep moving forward!
... Retired ...
Trâu đầm thì thế này được roài.Code:Amount: 10000 Execution Time: 20994 mili seconds Press any key to continue . . .
Với lại cái bài này tính nhiều chuỗi random làm cái gì, phi thực tế, tớ chả quan tâm.
Các bác siêu thuật toán cứ nghĩ tìm ra cách giải đi, rồi tớ xài
Nghĩ làm chi cho mệt
None!
cách này thử với 1 triệu phần tử chậm cực kỳ luôn (chắc chỉ nhanh hơn cách của mình lúc đầu)
- Bài này đúng là phi thực tế thiệt . nhưng nó áp dụng để test mảng băm trong bài tập lớn mình đang phải làm : cho người dùng nhập N chuổi vào mảng băm (chương trình sẽ tự random ra N chuỗi, chứ nếu để người dùng nhập 1 triệu chuỗi vào đó chắc chết )