1．Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and
another integer x, determines whether or not there exist two elements in S whose sum is exactly x. (Implement exercise 2.3-7.)
#include<stdio.h>
#include<stdlib.h>
void merge(int arr[],int low,int mid,int high){
int i,k;
int *tmp=(int*)malloc((high-low+1)*sizeof(int));
int left_low=low;
int left_high=mid;
int right_low=mid+1;
int right_high=high;
for(k=0;left_low<=left_high&&right_low<=right_high;k++)
{
if(arr[left_low]<=arr[right_low]){
tmp[k]=arr[left_low++];
}
else{
tmp[k]=arr[right_low++];
}
}
if(left_low<=left_high){
for(i=left_low;i<=left_high;i++){
tmp[k++]=arr[i];
}
}
if(right_low<=right_high){
for(i=right_low;i<=right_high;i++)
tmp[k++]=arr[i];
}
for(i=0;i<high-low+1;i++)
arr[low+i]=tmp[i];
}
void merge_sort(int a[],int p,int r){
int q;
if(p<r){
q=(p+r)/2;
merge_sort(a,p,q);
merge_sort(a,q+1,r);
merge(a,p,q,r);
}
}
int main(){
int a[8]={3,5,8,6,4,1,1};
int i,j;
int x=10;
merge_sort(a,0,6);
printf("after Merging-Sort:\n");
for(i=0;i<7;i++){
printf("%d",a[i]);
}
printf("\n");
i=0;j=6;
do{
if(a[i]+a[j]==x){
printf("exist");
break;
}
if(a[i]+a[j]>x)
j--;
if(a[i]+a[j]<x)
i++;
}while(i<=j);
if(i>j)
printf("not exist");
system("pause");
return 0;
}
標簽：
c語言
算法
排序
上傳時間：
2017-04-01
上傳用戶：糖兒水嘻嘻
有兩種方式可以讓設備和應用程序之間聯系：1. 通過為設備創建的一個符號鏈；2. 通過輸出到一個接口WDM驅動程序建議使用輸出到一個接口而不推薦使用創建符號鏈的方法。這個接口保證PDO的安全，也保證安全地創建一個惟一的、獨立于語言的訪問設備的方法。一個應用程序使用Win32APIs來調用設備。在某個Win32 APIs和設備對象的分發函數之間存在一個映射關系。獲得對設備對象訪問的第一步就是打開一個設備對象的句柄。
用符號鏈打開一個設備的句柄為了打開一個設備，應用程序需要使用CreateFile。如果該設備有一個符號鏈出口，應用程序可以用下面這個例子的形式打開句柄：hDevice = CreateFile("\\\\.\\OMNIPORT3", GENERIC_READ | GENERIC_WRITE,FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL ,NULL);文件路徑名的前綴“\\.\”告訴系統本調用希望打開一個設備。這個設備必須有一個符號鏈，以便應用程序能夠打開它。有關細節查看有關Kdevice和CreateLink的內容。在上述調用中第一個參數中前綴后的部分就是這個符號鏈的名字。注意：CreatFile中的第一個參數不是Windows 98/2000中驅動程序(.sys文件)的路徑。是到設備對象的符號鏈。如果使用DriverWizard產生驅動程序，它通常使用類KunitizedName來構成設備的符號鏈。這意味著符號鏈名有一個附加的數字，通常是0。例如：如果鏈接名稱的主干是L“TestDevice”那么在CreateFile中的串就該是“\\\\.\\TestDevice0”。如果應用程序需要被覆蓋的I/O，第六個參數(Flags)必須或上FILE_FLAG_OVERLAPPED。
使用一個輸出接口打開句柄用這種方式打開一個句柄會稍微麻煩一些。DriverWorks庫提供兩個助手類來使獲得對該接口的訪問容易一些，這兩個類是CDeviceInterface, 和 CdeviceInterfaceClass。CdeviceInterfaceClass類封裝了一個設備信息集，該信息集包含了特殊類中的所有設備接口信息。應用程序能有用CdeviceInterfaceClass類的一個實例來獲得一個或更多的CdeviceInterface類的實例。CdeviceInterface類是一個單一設備接口的抽象。它的成員函數DevicePath()返回一個路徑名的指針，該指針可以在CreateFile中使用來打開設備。下面用一個小例子來顯示這些類最基本的使用方法：extern GUID TestGuid;HANDLE OpenByInterface( GUID* pClassGuid, DWORD instance, PDWORD pError){ CDeviceInterfaceClass DevClass(pClassGuid, pError); if (*pError != ERROR_SUCCESS) return INVALID_HANDLE_VALUE; CDeviceInterface DevInterface(&DevClass, instance, pError); if (*pError != ERROR_SUCCESS) return INVALID_HANDLE_VALUE; cout << "The device path is " << DevInterface.DevicePath() << endl;
HANDLE hDev; hDev = CreateFile( DevInterface.DevicePath(), GENERIC_READ | GENERIC_WRITE, FILE_SHARE_READ | FILE_SHARE_WRITE, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL ); if (hDev == INVALID_HANDLE_VALUE) *pError = GetLastError(); return hDev;}
在設備中執行I/O操作一旦應用程序獲得一個有效的設備句柄，它就能使用Win32 APIs來產生到設備對象的IRPs。下面的表顯示了這種對應關系。Win32 API DRIVER_FUNCTION_xxxIRP_MJ_xxx KDevice subclass member function CreateFile CREATE Create ReadFile READ Read WriteFile WRITE Write DeviceIoControl DEVICE_CONTROL DeviceControl CloseHandle CLOSECLEANUP CloseCleanUp 需要解釋一下設備類成員的Close和CleanUp：CreateFile使內核為設備創建一個新的文件對象。這使得多個句柄可以映射同一個文件對象。當這個文件對象的最后一個用戶級句柄被撤銷后，I/O管理器調用CleanUp。當沒有任何用戶級和核心級的對文件對象的訪問的時候，I/O管理器調用Close。如果被打開的設備不支持指定的功能，則調用相應的Win32將引起錯誤（無效功能）。以前為Windows95編寫的VxD的應用程序代碼中可能會在打開設備的時候使用FILE_FLAG_DELETE_ON_CLOSE屬性。在Windows NT/2000中，建議不要使用這個屬性，因為它將導致沒有特權的用戶企圖打開這個設備，這是不可能成功的。I/O管理器將ReadFile和WriteFile的buff參數轉換成IRP域的方法依賴于設備對象的屬性。當設備設置DO_DIRECT_IO標志，I/O管理器將buff鎖住在存儲器中，并且創建了一個存儲在IRP中的MDL域。一個設備可以通過調用Kirp::Mdl來存取MDL。當設備設置DO_BUFFERED_IO標志，設備對象分別通過KIrp::BufferedReadDest或 KIrp::BufferedWriteSource為讀或寫操作獲得buff地址。當設備不設置DO_BUFFERED_IO標志也不設置DO_DIRECT_IO，內核設置IRP 的UserBuffer域來對應ReadFile或WriteFile中的buff參數。然而，存儲區并沒有被鎖住而且地址只對調用進程有效。驅動程序可以使用KIrp::UserBuffer來存取IRP域。對于DeviceIoControl調用，buffer參數的轉換依賴于特殊的I/O控制代碼，它不在設備對象的特性中。宏CTL_CODE（在winioctl.h中定義）用來構造控制代碼。這個宏的其中一個參數指明緩沖方法是METHOD_BUFFERED, METHOD_IN_DIRECT, METHOD_OUT_DIRECT, 或METHOD_NEITHER。下面的表顯示了這些方法和與之對應的能獲得輸入緩沖與輸出緩沖的KIrp中的成員函數：Method Input Buffer Parameter Output Buffer Parameter METHOD_BUFFERED KIrp::IoctlBuffer KIrp::IoctlBuffer
METHOD_IN_DIRECT KIrp::IoctlBuffer KIrp::Mdl
METHOD_OUT_DIRECT KIrp::IoctlBuffer KIrp::Mdl
METHOD_NEITHER KIrp::IoctlType3InputBuffer KIrp::UserBuffer
如果控制代碼指明METHOD_BUFFERED，系統分配一個單一的緩沖來作為輸入與輸出。驅動程序必須在向輸出緩沖放數據之前拷貝輸入數據。驅動程序通過調用KIrp::IoctlBuffer獲得緩沖地址。在完成時，I/O管理器從系統緩沖拷貝數據到提供給Ring 3級調用者使用的緩沖中。驅動程序必須在結束前存儲拷貝到IRP的Information成員中的數據個數。如果控制代碼不指明METHOD_IN_DIRECT或METHOD_OUT_DIRECT，則DeviceIoControl的參數呈現不同的含義。參數InputBuffer被拷貝到一個系統緩沖，這個緩沖驅動程序可以通過調用KIrp::IoctlBuffer。參數OutputBuffer被映射到KMemory對象，驅動程序對這個對象的訪問通過調用KIrp::Mdl來實現。對于METHOD_OUT_DIRECT，調用者必須有對緩沖的寫訪問權限。注意，對METHOD_NEITHER，內核只提供虛擬地址；它不會做映射來配置緩沖。虛擬地址只對調用進程有效。這里是一個用METHOD_BUFFERED的例子：首先，使用宏CTL_CODE來定義一個IOCTL代碼：#define IOCTL_MYDEV_GET_FIRMWARE_REV \CTL_CODE (FILE_DEVICE_UNKNOWN,0,METHOD_BUFFERED,FILE_ANY_ACCESS)現在使用一個DeviceIoControl調用：BOOLEAN b;CHAR FirmwareRev[60];ULONG FirmwareRevSize;b = DeviceIoControl(hDevice, IOCTL_MYDEV_GET_VERSION_STRING, NULL, // no input 注意，這里放的是包含有執行操作命令的字符串指針 0, FirmwareRev, //這里是output串指針，存放從驅動程序中返回的字符串。sizeof(FirmwareRev),& FirmwareRevSize, NULL // not overlapped I/O );如果輸出緩沖足夠大，設備拷貝串到里面并將拷貝的資結束設置到FirmwareRevSize中。在驅動程序中，代碼看起來如下所示：const char* FIRMWARE_REV = "FW 16.33 v5";NTSTATUS MyDevice::DeviceControl( KIrp I ){ ULONG fwLength=0; switch ( I.IoctlCode() ) { case IOCTL_MYDEV_GET_FIRMWARE_REV: fwLength = strlen(FIRMWARE_REV)+1; if (I.IoctlOutputBufferSize() >= fwLength) { strcpy((PCHAR)I.IoctlBuffer(),FIRMWARE_REV); I.Information() = fwLength; return I.Complete(STATUS_SUCCESS); } else { } case . . . } }
標簽：
驅動程序
應用程序
接口
上傳時間：
2013-10-17
上傳用戶：gai928943
RSA算法 :首先, 找出三個數, p, q, r, 其中 p, q 是兩個相異的質數, r 是與 (p-1)(q-1) 互質的數...... p, q, r 這三個數便是 person_key，接著, 找出 m, 使得 r^m == 1 mod (p-1)(q-1)..... 這個 m 一定存在, 因為 r 與 (p-1)(q-1) 互質, 用輾轉相除法就可以得到了..... 再來, 計算 n = pq....... m, n 這兩個數便是 public_key ，編碼過程是, 若資料為 a, 將其看成是一個大整數, 假設 a < n.... 如果 a >= n 的話, 就將 a 表成 s 進位 (s
標簽：
person_key
RSA
算法
上傳時間：
2013-12-14
上傳用戶：zhuyibin
