Algorithm on n-bit matrix -

-

दो फ़ंक्शन P1, P2 दिए गए हैं जो इनपुट n-bit x , और y1 = A1 * x, y2 = A2 * x की गणना करें। ए 1 और ए 2 है n * n बिट मैट्रिक्स ये दो फ़ंक्शन n-bit सरणी y1, y2 देता है। हम इन मैट्रिक्स के बारे में कोई जानकारी नहीं जानते हैं लेकिन ए 1 और A2 एक स्लॉट (i, j) को छोड़कर ही पता है । ( i और j हमारे लिए अज्ञात हैं)। हम x के विभिन्न मान के लिए P1 और P2 को कॉल कर सकते हैं और फिर इन दो फ़ंक्शन के आउटपुट की तुलना कर सकते हैं। मुझे यह पता लगाना है कि हम कितने कॉलों के साथ i, j पा सकते हैं?

संक्षिप्त उत्तर में हमारी पुस्तक ने लिखा: लॉग n कॉल कोई संकेत या विचार? सभी के लिए धन्यवाद।

संपादित करें: कोई कहता है, पहले x पर "1 के" का एक स्तंभ मैट्रिक्स होना चाहिए। और y1 और y2 की गणना करें और उस पंक्ति को खोजें जो अलग है फिर x एक मैट्रिक्स बनें जो n / 2 ऊपर तत्व "1" और n / 2 तल तत्व "0 के" हो। अगर y1 और y2 बराबर अंतर n / 2 + 1 से n और हो 1 हो से n / 2 ...

आप कर सकते हैं यदि आप A1 और A2 :

को स्थानांतरित कर सकते हैं, तो आप दो कॉल में यह कर सकते हैं: जांचें कि y1 और y2 में प्रवेश अलग है। यह आपको i देता है।

ट्रांस्पेश <कोड> ए 1 और ए 2 , ऐसा ही करें, जो प्रविष्टि अलग है वह इंडेक्स है j का

स्थानांतरण के बिना: आप अभी भी i को निर्धारित करने के लिए एक गुणा करते हैं। अब, सिर्फ एक "द्विआधारी खोज" करें जहां आपके खोज क्षेत्र को 1 से आपके x वेक्टर के प्रवेश में पहचाना जाएगा।

पहला कदम: x वाले के साथ 1 के आधे को भरें, दूसरे वाला 0 , गुणा करें, जांचें कि क्या सूचकांक i पर प्रविष्टि अलग है, यदि यह नहीं है, तो आपका j दूसरी छमाही में है, यदि यह अलग है, तो यह आपके पहले छमाही में है (जिसे आप 1 के साथ महसूस किया था)

दूसरा चरण: दो चरणों में से पिछले चरण के चयनित हिस्सों में से एक को विभाजित करें, इसका एक आधा 1 से करें और दूसरा 0 के साथ, एक ही तर्क को दोहराने तक, जब तक आप एक ही प्रविष्टि के साथ नहीं छोड़ते वह एक आपके j

का सूचकांक है, चूंकि आप हमेशा 2 में विभाजित हैं, आपके पास बिल्कुल लॉग (n) कॉल होगा। 

  एक कॉल करने से `i` प्रविष्टि निर्धारित करें (तुच्छ) लंबाई = n / 2 start = 0 जबकि (नहीं मिला) var x [start..start + लंबाई] = 1 (0 सभी ओटर प्रविष्टियां) यदि परिणाम 1 [i] == परिणाम 2 [i] प्रारंभ = 0 लंबाई = लंबाई / 2 और शुरू = लंबाई + 1 लंबाई = लंबाई / 2 यदि लंबाई == 1 पाया। आपका सूचकांक जम्मू है

Comments

Post a Comment

Popular posts from this blog

c# - SignalR: "Protocol error: Unknown transport." when navigating to hub -

-
Image
I am trying to use the ASP.NET signal for the first time - here's what I did: created a new web Has been added to the project and the following signal R packages: I have created the following category: [Hub-name ("chat")] Public class ChatHub: Hub {Public Zero Halo () {Clients.All.hello ( ); }} and the following startup configuration: public partial class startup {public zero configuration (IAppBuilder app) {configure (app); App.MapSignalR (); }} However, whenever I navigate localhost: (port) / api / signalr / chat I get the following error: Protocol error: Unknown transport. I am running a new browser and trying different people so remove it from the API / URL, and just use the localhost: (potter) / signaller / Chat
Read more

class - Kivy: how to instantiate a dynamic classes in python -

-
Using KV lang on my Python code, I have taken a hard time trying to instantiate a dynamic class, the following Consider the code: My test.kv file looks like this: & lt; MyPopup @ popup: Title: 'Hello' size_hunt: (1, .6) Grid layout: ID: RouteGrid column: 2 padding: ['8dp', '4dp', '8dp', '4dp'] Difference: '8dp' label: text: 'some text here' button: text: 'OK' On_press: do_something () & lt; MyGrid & gt;: Rows: 1 Button: Text: 'Show Popup' on_press: root.pop.show () Then import Kivy.app into my test.py: I get the following error: raise Factory Exception ('Uncount Class' '% name) kivy.factory.FactoryException: Unknown class Can anyone tell me how to do this properly, what do I remember? If you need more information please let me know Thank you. Takes a call to the factory before the KV file is loaded, so you want the class to Are not yet in existence. As long as no clas...
Read more

python - mayavi mapping a discrete colorbar on a surface -

-
Image
I want to change the color of the surface on the basis of another value (an ID) that is considered discrete (hence I In the simplified example given below, I have prepared a field with 3 different IDs: 0 / red on left 2 / blue 1 / green left But with the code below, I have some strange behavior on the border between red and blue (green Point) I think this is probably due to an interpolation! Code: import from import mlab np # np # my dataset -simplified-x, y, z = np.mgrid [-3: 3: 100] H, -3: 3: 100h, -3: 3: 100 h] value = NP. SQLT (x ** 2 + y ** 2 + z ** 2) # My color value: Volume is divided into 3 sub-versions taking colorvalues ​​with X = np.empty (values.shape) colorvalues [0:33,:,:] = 0 colorvalues ​​[33:66,:,:] = 2. Look [66:,:,:] = 1 src = mlab.pipeline.scalar_field (value) src.image_data.point_data.add_array (colorvalues.T.ravel ()) (1) .name = 'MyID' src.image_data. point_data.update src.image_data.point_data.get_array () # surface, contour = mlab.pipe...
Read more