Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 18 kết quả

Đề tài: Tạo một chuỗi ngẫu nhiên không trùng lặp trong lập trình C#

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    48

    Mặc định Tạo một chuỗi ngẫu nhiên không trùng lặp trong lập trình 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:
    1. //tạo mới một mảng các ký tự sẽ được chứa trong chuỗi
    2. 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'};
    3.  
    4. //tạo một chuỗi ngẫu nhiên
    5. Random fr = new Random();
    6.             string chuoi="";
    7.             for (int i = 0; i < 6; i++)
    8.             {
    9.                 int t = fr.Next(0, MangKyTu.Length);
    10.                 chuoi = chuoi + MangKyTu[t];
    11.             }


    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

  2. #2
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    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.

  3. #3
    Ngày gia nhập
    11 2007
    Bài viết
    48

    Trích dẫn Nguyên bản được gửi bởi NT_OnlyLove Xem bài viết
    Dùng sigle linklist đi, được đó.
    bạn có thể nói rõ hơn được không vậy. Thanks

    thầy mình đòi tối đa 1 triệu phần tử cơ (mới có 100.000 mà đã chậm rồi, lên đến 1triệu chắc đợi cả buổi)
    Đã được chỉnh sửa lần cuối bởi vinhson : 11-03-2008 lúc 08:07 PM.

  4. #4
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Đề bài của bạn ý như thế này phải không?
    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
    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.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  5. #5
    Ngày gia nhập
    10 2007
    Nơi ở
    HCMUNS
    Bài viết
    459

    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 ...

  6. #6
    Ngày gia nhập
    03 2008
    Bài viết
    3

    Mặc định Tạo một chuỗi ngẫu nhiên không trùng lặp trong lập trình C#

    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.

  7. #7
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    Viết một bản nháp đơn giản
    Visual C# Code:
    1.    class RandomGenerator
    2.     {
    3.         public const int DEFAULT_CAPACITY = 6;
    4.         private string[] _store;
    5.         private Random _rdmizer;
    6.         private int _capacity;
    7.         private static int _current = 0;
    8.  
    9.         /*
    10.          * PROPERTIES
    11.          */
    12.         public int Capacity
    13.         {
    14.             get { return _capacity; }
    15.             set { this._capacity = value; }
    16.         }
    17.  
    18.         public int Current
    19.         {
    20.             get { return _current; }
    21.         }
    22.  
    23.         /*
    24.          * CONSTRUCTOR
    25.          */
    26.         public RandomGenerator()
    27.         {
    28.             _store = new string[100];
    29.             for (int cnt = 0; cnt < 100; cnt++)
    30.                 _store[cnt] = "";
    31.             _rdmizer = new Random();
    32.             _capacity = DEFAULT_CAPACITY;
    33.         }
    34.  
    35.         /*
    36.          * METHODS
    37.          */
    38.  
    39.         // Just only use to generate a random string
    40.         public string Generate()
    41.         {
    42.             StringBuilder builder = new StringBuilder();
    43.             while (builder.Length < _capacity)
    44.             {
    45.                 builder.Append(_GenerateChar());
    46.             }
    47.             return builder.ToString();
    48.         }
    49.  
    50.         // Add a string to store
    51.         public void Add(string _in_str)
    52.         {
    53.             _store[_current++] = _in_str;
    54.         }
    55.         // Generate the next string to the store
    56.         public string Next()
    57.         {
    58.             string _str = Generate();
    59.             if (IsStored(_str) == true)
    60.                 Next();
    61.             Add(_str);            
    62.             return _str;            
    63.         }
    64.         // check whether a string stored already
    65.         public bool IsStored(string _in_str)
    66.         {
    67.             for (int _cnt = 0; _cnt < _store.Length; _cnt++)
    68.             {
    69.                 if (_store[_cnt].CompareTo(_in_str) == 0)
    70.                     return true;
    71.             }
    72.             return false;
    73.         }
    74.         // get all stored strings
    75.         public string[] GetStore()
    76.         {
    77.             return _store;
    78.         }
    79.         // generate a random character
    80.         private char _GenerateChar()
    81.         {
    82.             int _num;
    83.             do
    84.             {
    85.                 _num = _rdmizer.Next(48,122);
    86.             } while ((_num < 48) || (_num > 57 && _num < 65) || (_num > 90 && _num < 97));
    87.            
    88.             char chr = Convert.ToChar(_num);            
    89.             return chr;
    90.         }        
    91.     }

    Rồi test thử:
    Visual C# Code:
    1. class Program
    2.     {
    3.         static void Main(string[] args)
    4.         {
    5.             RandomGenerator generator = new RandomGenerator();
    6.             string start = generator.Generate();
    7.             Console.WriteLine("Start: " + start);
    8.             for (int cnt = 0; cnt < 10; cnt++)
    9.                 generator.Next();
    10.             string[] store = generator.GetStore();
    11.             for (int cnt = 0; cnt < store.Length && store[cnt] != ""; cnt++)
    12.                 Console.WriteLine("Store: " + store[cnt]);
    13.         }
    14.     }

    Kết quả:
    Code:
    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 . . .
    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 code

    + 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!

  8. #8
    Ngày gia nhập
    10 2007
    Nơi ở
    HCMUNS
    Bài viết
    459

    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 ...

  9. #9
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    Trích dẫn Nguyên bản được gửi bởi nhc1987 Xem bài viết
    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 ?
    Code:
    Amount: 10000
    Execution Time: 20994 mili seconds
    Press any key to continue . . .
    Trâu đầm thì thế này được roài.
    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!

  10. #10
    Ngày gia nhập
    11 2007
    Bài viết
    48

    Trích dẫn Nguyên bản được gửi bởi Xcross87 Xem bài viết
    Viết một bản nháp đơn giản
    [code=CSharp]

    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 code

    + 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 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 )

Các đề tài tương tự

  1. Tạo 1 chuỗi ngẫu nhiên cực mạnh trong lập trình C#
    Gửi bởi neverland87 trong diễn đàn Tutorials và Thủ thuật lập trình C#, ASP.NET
    Trả lời: 6
    Bài viết cuối: 04-07-2014, 10:46 AM
  2. Lập trình C++ Cách sử dụng hàm random để tạo số ngẫu nhiên không trùng nhau?
    Gửi bởi reach_phan trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 10-11-2011, 09:53 PM
  3. Hướng dẫn hàm tạo chuỗi ngẫu nhiên trong C++
    Gửi bởi bigcat2009 trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 0
    Bài viết cuối: 06-09-2010, 05:08 PM
  4. Tạo số ngẫu nhiên không trùng nhau lưu vào mảng?
    Gửi bởi icde trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 20-09-2009, 09:55 PM
  5. [ Solved ]Tạo số ngẫu nhiên không trùng nhau
    Gửi bởi jacking_nguyen1 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 31
    Bài viết cuối: 23-09-2008, 06:41 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn