Cần trợ giúp về thuật toán để giải quyết chỉ mục thông qua mảng bị lởm chởm

Question

Argh! Tôi biết tôi sẽ nhận được điều này cuối cùng nhưng vào thời điểm này tôi gần như 2 giờ vào nó và vẫn còn bị mắc kẹt.

Tôi cần phải giải quyết các chỉ mục riêng lẻ cho từng "mức" của một mảng răng cưa cho một vị trí cụ thể. Thật khó để giải thích, nhưng nếu bạn tưởng tượng một mảng răng cưa 3 cấp có độ dài [2,3,4]. Nếu bạn sau đó đã flatten rằng ra thành một mảng duy nhất nó sẽ có một kích thước 24. Bây giờ, chúng ta hãy nói rằng bạn cần phải tìm các chỉ số (một cho mỗi cấp độ của các mảng răng cưa) mà sẽ bằng chỉ số mảng duy nhất 22. Nó sẽ là 1,2,1. Nó không khó để tìm ra một kịch bản duy nhất, nhưng tôi đang cố gắng tìm ra những gì các thuật toán là để giải quyết các giá trị này cho một mảng sâu răng cưa biến.

Đây là một mẫu mã đơn giản của nỗ lực hiện tại của tôi:

using System; 

class Program 
{ 
    static void Main(string[] args) 
    { 
     // Build up the data and info about level depth 
     int[] levelDepth = new[] { 2, 3, 4 }; 
     int[][][] data = new int[][][] 
     { 
      new int[][] { new int[4], new int[4], new int[4] }, 
      new int[][] { new int[4], new int[4], new int[4] } 
     }; 

     int requestedValue = 22; 
     float temp = requestedValue; 

     // Store the index of each level array to get to the index 
     // for the requested value 
     int[] levelIndexes = new int[3] { 0, 0, 0 }; 

     // The following does not work! 
     int i = levelDepth.Length; 
     while (i > 0) 
     { 
      temp = temp/levelDepth[i - 1]; 
      levelIndexes[i - 1] = (int)Math.Round(temp); 

      i--; 
     } 
    } 
} 

Nó không làm việc một cách chính xác, mặc dù nó hầu như được tôi những gì tôi cần, nhưng tôi nghĩ rằng có thể chỉ là may mắn. Tôi nghi ngờ đây là một vấn đề phổ biến đã được giải quyết trước đây, tôi chỉ không có kinh nghiệm để tìm ra nó. Ngoài ra, trước khi bất cứ ai nói với tôi rằng sử dụng mảng như thế này là khủng khiếp hoặc "tại sao bạn không lưu trữ dữ liệu của bạn như thế này" - Mô tả và mã trên mô phỏng bố cục của một số chip giải mã trên phần cứng của chúng tôi và Tôi cần phải làm việc ra một cách để giải quyết một con đường đến một đồ thị cụ thể của các tầng cascading, ví dụ trên chính xác phù hợp với cách bố trí của các chip.Tôi đang bị mắc kẹt với nó ..

Answer 1

Bạn không nên sử dụng float s tại đây.

int[] levelDepth = new[] { 2, 3, 4 }; 
int requestedValue = 22; 
int[] levelIndexes = new int[levelDepth.Length]; 


for (int i = 0; i < levelDepth.Length; i++) 
{ 
    // need to go from { 2, 3, 4 } -> { 3*4, 4, 1 } 
    int f = 1; 
    for (int j = i+1; j < levelDepth.Length; j++)  
    f *= levelDepth[j]; 

    levelIndexes[i] = requestedValue/f; // integer divide 
    requestedValue = requestedValue % f; 
} 

Answer 2

Giả sử bạn cần giá trị của phần tử tại điểm đó (và không phải chỉ số cụ thể), bạn có thể chỉ cần thực hiện một số ruby ​​giống như flatten và sau đó truy cập trực tiếp vào chỉ mục. m Microsoft Visual C# .NET 2003 Developers Cookbook (Mác Schmidt):

static int[] GetDimensionIndices(int flatIndex, Array array) 
{ 
    int[] indices = new int[array.Rank]; 
    int p = 1; 
    for(int i = array.Rank - 1; i >= 0; i--) 
    { 
     indices[i] = (((flatIndex/p)) % (array.GetUpperBound(i)+1)); 

     if(i > 0) 
      p *= array.GetUpperBound(i) + 1; 
    } 
    return indices; 
} 

Answer 3

mảng có độ dài 2 giữ mảng có độ dài 3, nắm giữ mảng có độ dài 4.

Như vậy, chỉ số trên mảng đầu tiên sẽ tăng tổng chỉ mục của bạn lên 3 * 4 = 12.

Index trên mảng thứ hai sẽ tăng tổng số của bạn bằng cách 4.

Index trên mảng thứ ba sẽ tăng tổng số của bạn bằng cách 1.

Vì vậy, 22 = 12 * 1 + 4 * 2 + 1 * 1.

Sau khi tìm ra những con số này (nhân giá trị trong levelDepth với nhau), bạn có thể chỉ cần sử dụng thuật toán tham lam bắt đầu với mảng ngoài cùng.

int temp = requestedValue; 
int levelWeight[] = {levelDepth[2]*levelDepth[1], levelDepth[2], 1}; 
for(int i=0;i<3;i++){ 
    while(requestedValue >= levelWeight[i]){ 
     levelIndexes[i]++; 
     requestedValue-=levelWeight[i]; 
    } 
}