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

Camel ProducerTemplate possible memory leak -

-
To some degree, this is a bit of a shot in the dark, but we have a process that is dramatically slow One day's course we have found that all the things running on the fuses begin to draw, but when we are running a specific process, JPPropellers are going on, I have found that the increase in magnetic usage increases over time. . Org.apache.camel.ProductTemplate.Send So my main question is, is the way in which the manufacturer product is being used here which is wrong / can this be a problem? exchange foo = new DefaultExchange (getCamelContext (), ExchangePattern.InOnly); Foo.getIn () setBody (obj). Root R = Exchange .getContext (). GetRoute ("do_something_fun"); Creator Template Template = exchange.getContext () CreateProducerTemplate (); Template.send (r.getEndpoint (), foo); Generally, you should not create a productive template on each request as described here: / P> However, because I do not have a complete picture of your application, so you can cr...
Read more

javascript - Adhering to a max length setting with jshint -

-
I get several recommendations to compile a maximum of 80 characters when writing javascript, e.g. Google, NPM, Node. JS, Crockford In some cases, though, I do not think how best to do this. MongoClient.connect ('mongodb: // localhost: 27017 / sampleDatabase', function (mistake, database) {if (err)} {throw error;} db = database;}); This will throw a jshint warning because it exceeds 80 characters. Now, do you choose to ignore the warning in this example, or instead choose an option for a solution like MongoClient.connect ('mongodb: // localhost: 27017 / sampleDatabase' , Function (err, database) {if (err) {throw error;} db = database;}); If you can reuse the url variable So, great option if this is a shot, as is often such a call, I would probably do something like this ... / * jslint sloppy: true, white: true, browser: True, maxlen: 80 * / / * global mongo client * / var dbarhh, db; DbErrHand = function (mistake, database) {if (err) {throw error; } ...
Read more