| 随机数 |
c++基础 |
|
#include <math.h>
/* variables are declared static so that they cannot conflict
with names of */
/* other global variables in other files. See K&R, p 80, for
scope of static */
static double oldrand[55]; /* Array of 55
random numbers */
static int jrand; /*
current random number */
static double rndx2; /* used with random
normal deviate */
static int rndcalcflag; /* used with random
normal deviate */
advance_random()
/* Create next batch of 55 random numbers */
{
int j1;
double new_random;
for(j1 = 0; j1 < 24; j1++)
{
new_random = oldrand[j1] - oldrand[j1+31];
if(new_random < 0.0) new_random = new_random + 1.0;
oldrand[j1] = new_random;
}
for(j1 = 24; j1 < 55; j1++)
{
new_random = oldrand [j1] - oldrand [j1-24];
if(new_random < 0.0) new_random = new_random + 1.0;
oldrand[j1] = new_random;
}
}
int flip(prob)
/* Flip a biased coin - true if heads */
float prob;
{
float randomperc();
if(randomperc() <= prob)
return(1);
else
return(0);
}
initrandomnormaldeviate()
/* initialization routine for randomnormaldeviate */
{
rndcalcflag = 1;
}
double noise(mu ,sigma)
/* normal noise with specified mean & std dev: mu & sigma */
double mu, sigma;
{
double randomnormaldeviate();
return((randomnormaldeviate()*sigma) + mu);
}
double randomnormaldeviate()
/* random normal deviate after ACM algorithm 267 / Box-Muller Method */
{
double sqrt(), log(), sin(), cos();
float randomperc();
double t, rndx1;
if(rndcalcflag)
{
rndx1 = sqrt(- 2.0*log((double) randomperc()));
t = 6.2831853072 * (double) randomperc();
rndx2 = sin(t);
rndcalcflag = 0;
return(rndx1 * cos(t));
}
else
{
rndcalcflag = 1;
return(rndx2);
}
}
float randomperc()
/* Fetch a single random number between 0.0 and 1.0 - Subtractive Method */
/* See Knuth, D. (1969), v. 2 for details */
/* name changed from random() to avoid library conflicts on some machines*/
{
jrand++;
if(jrand >= 55)
{
jrand = 1;
advance_random();
}
return((float) oldrand[jrand]);
}
int rnd(low, high)
/* Pick a random integer between low and high */
int low,high;
{
int i;
float randomperc();
if(low >= high)
i = low;
else
{
i = (randomperc() * (high - low + 1)) + low;
if(i > high) i = high;
}
return(i);
}
float rndreal(lo ,hi)
/* real random number between specified limits */
float lo, hi;
{
return((randomperc() * (hi - lo)) + lo);
}
warmup_random(random_seed)
/* Get random off and running */
float random_seed;
{
int j1, ii;
double new_random, prev_random;
oldrand[54] = random_seed;
new_random = 0.000000001;
prev_random = random_seed;
for(j1 = 1 ; j1 <= 54; j1++)
{
ii = (21*j1)%54;
oldrand[ii] = new_random;
new_random = prev_random-new_random;
if(new_random<0.0) new_random = new_random + 1.0;
prev_random = oldrand[ii];
}
advance_random();
advance_random();
advance_random();
jrand = 0;
}
/*-------------------------------------------------------------*/
|
| 链表练习 |
c++基础 |
|
#include "stdlib.h"
#include "stdio.h"
#include <iostream>
#include <Windows.h>
#define MaxSize 1000
using namespace std;
typedef struct node
{
int num;
node * lchild;
node * rchild;
};
struct chain
{
node * p;
chain * next;
}*head;
typedef struct Stack
{
int data[MaxSize];
int top;
};
void postOrder(node *T,Stack s){
if(T != NULL)
{
s.top++;
s.data[s.top] = T->num;
if(T->lchild == NULL && T->rchild == NULL){
for(int i = s.top; i > 0; i--){
cout << s.data[i];
}
cout << endl;
}
postOrder(T->lchild,s);
postOrder(T->rchild,s);
}
}
//每次新添加的节点加入链表尾部。
void AddNode(int Num){
node * NewNode = (node*)calloc(1,sizeof (node));
NewNode->num = Num;
node * FatherNode = head->p;
if(FatherNode->lchild == NULL)
FatherNode->lchild = NewNode;
else if(FatherNode->rchild == NULL){
FatherNode->rchild = NewNode;
//如果右节点也添加了，则链表头移到下一个
head = head->next ;
}
else
return;
chain *tail = head;
//找到链表尾
while (tail->next != NULL)
tail = tail->next;
//添加新节点到链表尾
chain *Newtail = (chain*)calloc(1,sizeof (chain));
Newtail->p = NewNode;
tail->next = Newtail;
}
int main()
{
//根节点
int k = 0; // k层
node * root=(node*)calloc(1,sizeof (node));
root->num=1;
head=(chain*)calloc(1,sizeof (chain));
head->p =root;
head->next =NULL;
cout << "请输入N（N个二进制位，取值范围大于等于1）:" << endl;
cin >> k;
k = pow(2.0,k + 1) - 1;
for(int N = 2;N <= k;N++){
int tmp = N % 2;
AddNode(tmp);
}
Stack s;
s.top = -1;
postOrder(root,s);
system("pause");
return 0;
}
|
| 图的邻接表存储结构 |
c++基础 |
|
/************************************************************************/
/* 图的邻接表存储结构 */
/************************************************************************/
#ifdef _MSC_VER
#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>
#ifdef _DEBUG
#define new new(_NORMAL_BLOCK, __FILE__, __LINE__)
#endif
#endif
#include <stdio.h>
#define MaxVertexNum 100
#define QueueSize 30
typedef enum{ FALSE, TRUE }Boolean;
Boolean visited[MaxVertexNum];
typedef char VertexType;
typedef int EdgeType;
typedef struct node //边表结点
{
int adjvex; //邻接点域
struct node *next; //域链
//若是要表示边上的权,则应增加一个数据域
}EdgeNode;
typedef struct vnode //顶点边结点
{
VertexType vertex; //顶点域
EdgeNode *firstedge;//边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型
typedef struct
{
AdjList adjlist; //邻接表
int n, e; //图中当前顶点数和边数
}ALGraph; //对于简单的应用，无须定义此类型，可直接使用AdjList类型
/************************************************************************/
/* 建立无向图的邻接表算法 */
/************************************************************************/
void CreateGraphAL(ALGraph *G)
{
int i, j, k;
EdgeNode * s;
printf("请输入顶点数和边数(输入格式为:顶点数,边数)：\n");
scanf("%d,%d", &(G->n), &(G->e)); // 读入顶点数和边数
printf("请输入顶点信息(输入格式为:顶点号<CR>)每个顶点以回车作为结束:\n");
for (i = 0; i < G->n; i++) // 立有n个顶点的顶点表
{
scanf("\n%c", &(G->adjlist[i].vertex)); // 读入顶点信息
G->adjlist[i].firstedge = NULL; // 点的边表头指针设为空
}
printf("请输入边的信息(输入格式为:i,j)：\n");
for (k = 0; k < G->e; k++) // 建立边表
{
scanf("\n%d,%d", &i, &j); // 读入边<Vi,Vj>的顶点对应序号
s = new EdgeNode; // 生成新边表结点s
s->adjvex = j; // 邻接点序号为j
s->next = G->adjlist[i].firstedge; // 将新边表结点s插入到顶点Vi的边表头部
G->adjlist[i].firstedge = s;
s = new EdgeNode;
s->adjvex = i;
s->next = G->adjlist[j].firstedge;
G->adjlist[j].firstedge = s;
}
}
/************************************************************************/
/* 深度优先遍历 */
/************************************************************************/
void DFS(ALGraph *G, int i)
{
//以vi为出发点对邻接表表示的图G进行深度优先搜索
EdgeNode *p;
printf("visit vertex:%c\n", G->adjlist[i].vertex); // 访问顶点vi
visited[i] = TRUE; //标记vi已访问
p = G->adjlist[i].firstedge; //取vi边表的头指针
while (p)
{ //依次搜索vi的邻接点vj，这里j=p->adjvex
if (!visited[p->adjvex]) //若vi尚未被访问
DFS(G, p->adjvex); //则以Vj为出发点向纵深搜索
p = p->next; //找vi的下一邻接点
}
}
void DFSTraverseM(ALGraph *G)
{
int i;
for (i = 0; i < G->n; i++)
visited[i] = FALSE;
for (i = 0; i < G->n; i++)
if (!visited[i])
DFS(G, i);
}
/************************************************************************/
/* 广度优先遍历 */
/************************************************************************/
typedef struct
{
int front;
int rear;
int count;
int data[QueueSize];
}CirQueue;
void InitQueue(CirQueue *Q)
{
Q->front = Q->rear = 0;
Q->count = 0;
}
int QueueEmpty(CirQueue *Q)
{
return Q->count == 0;
}
int QueueFull(CirQueue *Q)
{
return Q->count == QueueSize;
}
void EnQueue(CirQueue *Q, int x)
{
if (QueueFull(Q))
printf("Queue overflow");
else
{
Q->count++;
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % QueueSize;
}
}
int DeQueue(CirQueue *Q)
{
int temp;
if (QueueEmpty(Q))
{
printf("Queue underflow");
return NULL;
}
else
{
temp = Q->data[Q->front];
Q->count--;
Q->front = (Q->front + 1) % QueueSize;
return temp;
}
}
void BFS(ALGraph*G, int k)
{ // 以vk为源点对用邻接表表示的图G进行广度优先搜索
int i;
CirQueue Q; //须将队列定义中DataType改为int
EdgeNode *p;
InitQueue(&Q); //队列初始化
printf("visit vertex:%c\n", G->adjlist[k].vertex); //访问源点vk
visited[k] = TRUE;
EnQueue(&Q, k); //vk已访问，将其人队。（实际上是将其序号人队）
while (!QueueEmpty(&Q))
{ //队非空则执行
i = DeQueue(&Q); //相当于vi出队
p = G->adjlist[i].firstedge; //取vi的边表头指针
while (p)
{ //依次搜索vi的邻接点vj(令p->adjvex=j)
if (!visited[p->adjvex])
{ //若vj未访问过
printf("visit vertex:%c\n", G->adjlist[p->adjvex].vertex); //访问vj
visited[p->adjvex] = TRUE;
EnQueue(&Q, p->adjvex); //访问过的vj人队
}
p = p->next; //找vi的下一邻接点
}
}
}
void BFSTraverseM(ALGraph *G)
{
int i;
for (i = 0; i < G->n; i++)
visited[i] = FALSE;
for (i = 0; i < G->n; i++)
if (!visited[i])
BFS(G, i);
}
/************************************************************************/
/* 打印邻接表 */
/************************************************************************/
void PrintfGraphAL(ALGraph *G)
{
for (int i = 0; i < G->n; i++)
{
printf("vertex:%c", G->adjlist[i].vertex);
EdgeNode *p = G->adjlist[i].firstedge;
while (p)
{
printf("→:%d", p->adjvex);
p = p->next;
}
printf("\n");
}
}
/************************************************************************/
/* 删除邻接表 */
/************************************************************************/
void DeleteGraphAL(ALGraph *G)
{
for (int i = 0; i < G->n; i++)
{
EdgeNode *q;
EdgeNode *p = G->adjlist[i].firstedge;
while (p)
{
q = p;
p = p->next;
delete q;
}
G->adjlist[i].firstedge = NULL;
}
}
/************************************************************************/
/* 主函数调用 */
/************************************************************************/
int main()
{
#ifdef _MSC_VER
_CrtSetDbgFlag(_CRTDBG_LEAK_CHECK_DF | _CrtSetDbgFlag(_CRTDBG_REPORT_FLAG));
_CrtDumpMemoryLeaks();
#endif
ALGraph G;
CreateGraphAL(&G);
printf("深度优先遍历：\n");
DFSTraverseM(&G);
printf("广度优先遍历：\n");
BFSTraverseM(&G);
printf("邻接表：\n");
PrintfGraphAL(&G);
DeleteGraphAL(&G);
return 0;
}
|
| 递归全排序 |
小算法 |
|
public class Order {
/**
* 递归全排序
*/
public static void main(String[] args) {
int[] a={1,2,3};
pai(a,0,a.length);
}
public static void pai(int[] a,int start ,int end){
if(start ==end){
for(int i=0;i<end;i++){ //输出语句
System.out.print(a[i]);
}
System.out.println();
}
else{
for(int c=start;c<end;c++){
int b=a[start];
a[start] =a[c]; //交换位置
a[c] =b;
pai(a,start+1,end);
b=a[start];
a[start] =a[c]; //返回到原来的样子
a[c] =b;
}
}
}
}
|
| 把十进制数转换成n进制的数 |
小算法 |
|
public class Transform {
/**
* 把十进制数转换成n进制的数
*/
public static void main(String[] args) {
change(1348,8);
}
public static void change(int x,int n){
int a = x%n;
x = x/n;
if(x>0){
change(x,n);
}
System.out.print(a+"");
}
public static String change(int x){ //10进制转换成2进制
int a ;
String ss=new String();
while(x!=0){
a=x%2;
x=x/2;
ss=a+ss;
}
return ss;
}
public static int TwoToTen(String str){//2进制转换成10进制
int ten=0;
int length=str.length();
for(int i=0;i<length-1;i++){
char j=str.charAt(i);
if(j=='1') ten=ten+1;
ten= ten*2;
}
if(str.charAt(length-1)=='1') ten+=1;
return ten;
}
}
|
| 奇怪的数字 |
小算法（蓝桥杯） |
|
public class Ea1 {
/**
* 奇怪的数字0 , 1 , 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,...
*/
public static void main(String[] args) {
int a=0,b=1,c=1;
for(int i=3;i<10;i++){
a=b; //第一个数
b=c; //第二个数
c=a+b; //第三个数
}
System.out.println(c);
System.out.println(sum(10));
}
public static int sum(int i){
return (i==2 ||i==3)?1:sum(i-1)+sum(i-2);
}
/*
* 其实用递归是最简单的。
*/
}
|
| 5个猴子分苹果 |
小算法（蓝桥杯） |
|
/**
* 5个猴子分苹果
*/
public class Apple {
public static void main(String[] args) {
System.out.println(sum(5));//sum是总数
}
public static int sum(int monkey){
return monkey==1?6:5*sum(monkey-1)+1;
}
/*主要在设置出口,入口和循环体。容易在出口和入口出错。但是循环体是主要的思路(在大体上把握)
* 开始点和结束点要把握好。即使变成最小的问题时再解决。
*/
}
|
| 奇怪的节目 |
小算法（蓝桥杯） |
|
public class JieMu {
/**
* 奇怪的节目
*/
public static void main(String[] args) {
int[] a = new int[10];
sum(0,a,10);
}
public static void sum(int i,int[] a,int total){
if(i == 10){ //输出语句
if(total == 100){
for(int j=0;j<a.length;j++){
System.out.print(a[j]);
}
System.out.println();
}
}else{
a[i]=1;
sum(i+1,a,total*2);
a[i] = 0;
sum(i+1,a,total-i-1);}
}
/*
* 深刻总结
*/
}
|
| abcd字符串字符的全排序 |
小算法 |
|
/**
* abcd字符串字符的全排序
* 递归
*/
public class Menu1 {
public static void getOne(int[] arr, int start,int end){
if(start==end){
for(int j=0;j<end;j++){ // 如果start==end说明已经排序结束了,输出
System.out.print(arr[j]);
}
System.out.print("\n");
}else{
for(int i=start;i<end;i++){
int temp=arr[start]; //
arr[start]=arr[i]; //
arr[i]=temp; //
getOne(arr, start+1,end);//将剩下的所有元素全排序;
temp=arr[start];
arr[start]=arr[i];
arr[i]=temp;
}
}
}
public static void main(String[] args) {
int[] arr={1,2,3};
getOne(arr,0,3);
}
}
|
| 模式匹配 |
小算法 |
|
public class Match {
/**
* 模式匹配
*/
public static void main(String[] args) {
String main = "12345amnbvcxzqwer"; //主串
String chong ="mnb"; //丛串
int i=0,j=0;
while(i<main.length() && j< chong.length()){
char ma =main.charAt(i);
char ch =chong.charAt(j);
if(ma ==ch){
i++;
j++;
}
else{
i = i-j+1; //要比较i的下一个位置,i和j都是从第一个0个位置
j=0; //c++是从第二个位置开始的所以要加2
}
}
if(j == chong.length()){
System.out.println(i-j);
}else{
System.out.println("不存在");
}
}
}
|
| 最大公约数和最小公倍数 |
最大公约数和最小公倍数 |
|
public static int deff(int x, int y) { //求连个数的最大公约数 ,非递归求法
int t;
if(x < y) { //得到x>y
t = x;
x = y;
y = t;
}
while(y != 0) {
if(x == y) return x;
else {
int k = x % y;
x = y;
y = k;
}
}
return x;
}
public static int getBa(int x,int y){ //求最小公倍数
return (x*y)/deff(x,y);
}
private long gcd(long a, long b){
if(b==0) return a;
return gcd(b,a%b); //利用递归求最大公约数
}
最大公约数和最小公倍数
|
| 全排列 |
全排列 |
|
int[] a={1,2,3};
pai(a,0,a.length); //对数组a中的数全排列,使用的递归排序法
public static void pai(int[] a,int start ,int end){
if(start ==end){
for(int i=0;i<end;i++){ //输出语句
System.out.print(a[i]);
}
System.out.println();
}
else{
for(int c=start;c<end;c++){
int b=a[start];
a[start] =a[c]; //交换位置
a[c] =b;
pai(a,start+1,end);
b=a[start];
a[start] =a[c]; //返回到原来的样子
a[c] =b;
}
}
}
|
| 求完数 |
求完数 |
|
System.out.println("1到1000的完数有： ");
for(int i=1; i<1000; i++) {
int t = 0;
for(int j=1; j<= i/2; j++) {
if(i % j == 0) {
t = t + j;
}
}
if(t == i) {
System.out.print(i + " ");
}
}
|
| 判断素数 |
判断素数 |
|
Scanner c = new Scanner(System.in);
int d= c.nextInt();
for(int i=2;i*i<=d;i++){ //使用i的平方大大降低了时间复杂度
if(d%i==0){
flg= false;
System.out.println("是素数");
break;
}
}
if(flg==true)
System.out.println("不是素数");
|
| 进制转化 |
进制转化 |
|
private static int getRealValue(char c){ //把对应的十六进制单个字符转化10进制数
if(c>='0'&&c<='9')
return c-'0';
if(c>='a'&&c<='f')
return c-'a'+10;
if(c>='A'&&c<='F'){
return c-'A'+10;
}
return 0;
}
public static String jin_zhi_16_3(String str){
int n=0;
for(int i=0;i<str.length();i++){
//n =16*n +getRealValue(str.charAt(i)); //根据16进制转化到10进制的算法
n = n + (int)Math.pow(16, str.length()-i-1)*getRealValue(str.charAt(i));
//下面是一种常规思想(需要调用java中Math方法)但是效率比较低，上面的不太好想
} //首先要了解进制的转化规律16*n经典写法
String t = "";
for(;;) {
if(n==0) break;
t = (n % 3) + t; //转化进制几就除以几
n = n/3; // 填空
}
return t;
}
|
| 大数求余 |
大数求余 |
|
private void input(){
Scanner c= new Scanner(System.in);
String str = c.nextLine();
int[] array = new int[str.length()];
for(int i=0;i<array.length;i++){ //把所输入的大数存放到数组中，然后求余
array[i] = Integer.parseInt(str.substring(i, i+1));
}
int d = c.nextInt();
getYushu(array,d);
}
private static void getYushu(int[] array,int d){
int digit=0;
for(int i=0;i<array.length;i++){
digit = (digit*10+array[i])%d;//这是按照正常的数学思想求余数
}
System.out.println(digit);
}
|
| 本地变量 |
|
|
public class ProjectContext {
/**
* 线程本地变量
*/
private static final ThreadLocal<String> threadlocal = new ThreadLocal<String>();
/**
* 设置工程名字
*/
public static void setProjectName(String name){
threadlocal.set(name);
}
/**
* 获取工程名字
* @return
*/
public static String getProjectName(){
return threadlocal.get();
}
/**
* 删除线程本地工程名
*/
public static void rmProjectName(){
threadlocal.remove();
}
}
|
